Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

2
votes
1answer
17 views

CFG for words that are not a concatenation of the same word [duplicate]

I am teaching myself formal languages, and yesterday i got stuck at an exercise asking for a context free grammar for the language: $ L = \{x \in \Sigma ^{+} | \ \forall w \in \Sigma ^{+} \ x \neq ...
0
votes
2answers
82 views

How do you find an infinite regular language that is a subset of a non-regular language?

In order to do this, we would probably need the non-regular language to be infinite as well, then find some definition for the non-regular language in order to fulfill the requirement, but I don't ...
0
votes
3answers
122 views

Is the empty string of even length?

There is this example of regular expressions: $$(\Sigma\Sigma)^*= \{w\mid |w|\text{ is even}\}\,.$$ From that I understand the empty string is valid as a string of even length. Is this true?
10
votes
3answers
2k views

Regular languages that can't be expressed with only 2 regex operations

I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but I have been told that you need all three of the regular ...
3
votes
1answer
56 views

Is no language with the non-primes property context-free?

A language $L$ is said to have the "no primes" property if: For every prime $p$ there are no words $w$ in $L$ s.t. $|w|=p$. For every non-prime $m$ there is at least one word $w\in L$ of length ...
1
vote
2answers
90 views

Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$?

Does the Context Free Language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.
3
votes
1answer
117 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
1
vote
1answer
44 views

Can $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ be pumped using the pumping lemma?

In order to show that $ \{A^nB^nA^nB^n \mid n \geq 0 \}$ isn't CFL, I was trying to use a pumping lemma this way: At first we assign $w= A^jB^jA^jB^j ,$ $(w^i=uv^ixy^iz), p<|vxy|, p<j.$ if ...
0
votes
3answers
75 views

Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

This is for formal-language-style regular expression and not about Unix-style regular expression. I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings ...
3
votes
4answers
87 views

How to determine if a regular language L* exists

I'm trying to make sense of regular languages, operations on them, and Kleene operations. Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that ...
1
vote
1answer
47 views

Language of words that begin and end with same symbol and have equal numbers of a's and b's

I wish to find the CFG for a language on two symbols (say a and b) whose words begin and terminate with the same symbol, and have equal quantities of a's and b's. What is the thought process I should ...
3
votes
0answers
30 views

What kind of formal language is generated by Parsing Expression Grammars?

I've been unable to find what language is recognized by PEGs. The original paper[1] only conjectures that there are some Context-Free Grammars that are unrecognizable by PEGs. It also demonstrates how ...
1
vote
1answer
68 views

What do you call a function from symbols of alphabet to languages?

Speaking of context-free (and maybe regular? or just any?) languages, what do you call a function defined as follows: Let $\Sigma$ be the alphabet of $L$, $\forall \sigma \in \Sigma: f(\sigma) = L'$, ...
3
votes
0answers
49 views

Proof $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic

Without using pumping lemma for deterministic context-free languages I need to prove that the language $\{u\colon |u| \text{ is odd and $b$ is in the middle}\}$ is not deterministic. Someone ...
0
votes
1answer
52 views

Why is $L=wxw^R|w,x\in\{0,1\}^+$ regular? [duplicate]

I was taught that if you can create a DFA to accept a language, then the grammar that is generating the language is regular. AND A DFA is a finite automata that accepts a language and also rejects ...
4
votes
1answer
41 views

Implementing regular expression matching using Brzozowski derivatives

I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. ...
0
votes
1answer
72 views

If a machine recognizes language L, can it also recognize L*?

This is a homework question. Suppose the only accept state is the start state. My rationale for this is that L* is just the concatenations of L, so if all strings in L are accepted, then all strings ...
-1
votes
0answers
43 views

How to solve a left-recursive Problem in grammar

I have a grammar like this and it has different type of problems 1) X -->YX|$ 2) Y --> ε|A|let A in Y|let A in E end 3) A--> x=E 4) E-->(E)|E*E|*E|EE|x|ƛx.E I tried to solve that and this my ...
8
votes
0answers
58 views

Using logic to prove non-regularity of a language

A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
3
votes
1answer
49 views

Does a DFA accept an empty string if $q_0$ is the accept state?

Suppose $q_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?
-3
votes
1answer
40 views

The language of all base-10 integers that are multiples of 9 [closed]

If I want to represent all the base 10 integers that are multiples of 9 as a language how do I do so? Alphabets are finite sets.
-4
votes
2answers
59 views

Are all irregular languages infinite?

How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.
-3
votes
1answer
31 views

Step by step method for generating Regular Expressions for languages [duplicate]

I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where: $L= \{w \in \{0, 1\}^{\ast} \mid \text{length of } w ...
-1
votes
0answers
45 views

How to prove the following language is not context-free? [duplicate]

I'm having trouble to get the whole point of the pumping lemma for CFL and how to write the proof correctly. I'll be happy to get some help to prove the following language is not a context-free: ...
-2
votes
2answers
48 views

Is the set of regular expressions over an alphabet equal to Σ*?

Are the following two sets equal? One the set of regular expression over an alphabet, and the other set is the set of all strings which can be generated by using the symbols of an alphabet(Σ*)?
4
votes
2answers
709 views

Is a single string enough to prove regular expressions inequivalent?

Which of the following regular expressions generate a language that is different from the rest? (a+b)$^*$a(a+b)$^*$(a+b)$^*$ b$^*$ab$^*$a(a+b)$^*$ (a+b)$^*$ab$^*$ab$^*$ ...
2
votes
1answer
97 views

Grammar of regular languages vs. context free languages

Let $L$ be some language. What could you say about $L$'s grammar if it is a regular language, that couldn't be said if it was a context free language? For example, in case $L$ is regular, could you ...
-3
votes
1answer
83 views

Showing that $\mathscr{L}$ is not context-free-grammar language

Let $"t"$ and $"s"$ be a words we will say that two words are "completly different" if for all $1\leq i\leq |t|$ the $i$ letter in $t$ diffrent from the $i$ letter in $s$. Prove that the language ...
0
votes
1answer
79 views

L=ww is not a CFL

I am studying CFL at the moment and I found this confusing. What I've just read is that, $L=\{ww\}$ is not a CFL. The proof showed it by using pumping lemma for CFL. ($w=0^n1^n0^n1^n$) and I fully ...
1
vote
3answers
86 views

Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

Table 4 in Problem Solving with Algorithms and Data Structures's chapter on Infix, Prefix and Postfix Expressions gives the following examples: ...
3
votes
1answer
18 views

Deriving from a terminal word in a context free grammar

Just to make it clear. (since my book doesn't mention anything like this) Suppose we have a context free grammar $G=(V,T,P,S)$. where $T=\{a,b\}$ (The other sets doesn't really matter). Since ...
3
votes
1answer
61 views

Proving that every derivation-tree has at most one leftmost-derivation in a context free grammar

I am trying to prove the following theorem: For every derivation-tree in a context-free grammar $G=(V,T,P,S)$ there exists at most one leftmost derivation. My partial proof by contradiction (I ...
2
votes
1answer
45 views

Using Context free language to simulate regular expression in finite automata

Is there a minimum number of non terminal we need to use in order to simulate a finite automata with n states? When we try to convert a language accepted by NFA to context free language, do we need n ...
3
votes
1answer
43 views

Lower bound for number of nonterminals in a CFG

Let's say we have a context-free grammar for the language $a\mbox{*}b\mbox{*}c\mbox{*}$. Is there a way to determine a lower bound for the number of nonterminals in this grammar? I'm pretty sure you ...
3
votes
1answer
66 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
0
votes
2answers
87 views

Context-free grammar for“not-at-all” palindromes

I need to bulid a context-free grammar for $\qquad \mathscr{L_4}=\{w\in\{a,b,c\}^* \mid w\text{ is not palindrome at all}\}$ Not palindrom at all: We will say that a word $w$ is not palindrome at ...
-1
votes
1answer
26 views

Unambiguous CFG that generates regular language according to Pumping Lemma?

The pumping lemma for regular languages states: Specifically, the pumping lemma says that for any regular language L there exists a constant p such that any word w in L with length at least p can ...
5
votes
1answer
69 views

Show that some context free languages must contain more that one non-terminal

Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular ...
-2
votes
1answer
42 views

All regular languages are context-free so why does the terminology not reflect that? [closed]

Since Regular languages $\subset$ Context-free languages, then Regular languages are Context-free languages? Why is the terminology so different then? To me these seem like a totally different class ...
0
votes
0answers
25 views

Growing context-sensitive grammars with context-free rules

Has anyone ever considered the class of languages $X$ generated by growing context-sensitive productions which are described by context-free rules? In particular, I wonder if there is a NP-complete ...
0
votes
3answers
77 views

Proving/Disproving that language L is non-regular/CFL

Here are three examples of questions I run into. I'm not looking for solutions. If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular. If $L$ is non-regular then $L' = \{ ww^R | w \in ...
5
votes
3answers
78 views

Terminology needed for the computational solution to the Rubik's Cube

I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology. Hello! I am currently writing a ...
1
vote
0answers
42 views

Use the pumping lemma to prove that {www} is not context-free

Use the pumping lemma to prove that the following language is not context-free. $\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$ I am studying for an exam and really trying to understand this question. ...
0
votes
1answer
36 views

Show Language is not context free without pumping lemma [duplicate]

Can we show that following language is not context free using Push down automata approach? L = {a^i b^i a^i : i>=1} For every a we will Push 'A' onto stack, ...
0
votes
1answer
92 views

Proving that two sets of strings are equal

I am stucked at this problem: Let $A=(\Sigma, Q, q_1, F, \delta)$ be a finite deterministic automaton (I.e. $\delta:Q\times\Sigma\to Q$) such that $Q=\{q_1,...,q_m\}$. Let's define foreach ...
2
votes
2answers
140 views

Is {wxw^r} a regular language?

Is $\{ WxW^{\mathrm{R}} \mid W,x\in\{0,1\}^+\}$ a regular language? If so, why? The notation $W^{\mathrm{R}}$ means the reverse string of $W$? If we consider the best answer in this solution, ...
0
votes
0answers
33 views

How to prove that the language of words ucv with as many a's in u as b's in v is irregular?

I'm trying to prove that: $L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$ is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far: ...
-1
votes
1answer
63 views

Language of Palindrome-Prefixed Words

Classify the language $L = \{xx^Rw\ \big|\ (|x| \geq 0\ \wedge |w|\gt 0)\ where\ x,w\in\Sigma^*\}$ as one of: Regular but not Context-Free Context-Free but not Regular Decidable ...
0
votes
1answer
22 views

There is any notation for a language that is empty infinite?

Assume that $L$ is a language, is there any established notation that means that $L$ is infinite or empty?
1
vote
1answer
42 views

Why does the concatenation of the empty set with any language give the empty set? [duplicate]

Why does the concatenation of $\emptyset$ with any language give $\emptyset$. I would like to know the intuitive explanation for it.