Questions about the set of languages (equivalently) described by context-free grammars or accepted by (non-deterministic) pushdown automata.

learn more… | top users | synonyms

1
vote
1answer
29 views

How to use the Pumping Lemma to prove that a restricted subset of 0*1*2*3*, where there are as many 3's as 0's and 1's, is not a CFL?

Use the pumping lemma for context-free languages to show that the following language is not context-free: $ L = \{0^i 1^j 2^i 3^k \mid k=i+j \} $ So I have started like this: Let us assume ...
3
votes
1answer
43 views

Is the word problem of CFLs in NC?

Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string. Lets say I have a ...
0
votes
1answer
31 views

The Chomsky–Schützenberger representation theorem

I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give ...
3
votes
0answers
44 views

Context free grammar as minimal solution of a system of equations

It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example: $$\begin{align*} X &=\{{\epsilon}\} \cup Y\\ X ...
3
votes
1answer
31 views

How to recursively infer a word/string from a context-free grammar?

Give the recursive inference of the word $abcddd$ from the Context-free Grammar: $A\rightarrow aAd\mid B$ $B\rightarrow bBd\mid C$ $C\rightarrow cC\mid cD$ $D\rightarrow Dd\mid ϵ$ This ...
-3
votes
0answers
24 views

PDA to CFG equivalence (No. of states and stack symbols)

All examples of problems on converting PDA to CFG I have encountered ALWAYS have a NUMBER of STATES EQUAL to the STACK SYMBOLS. Is that always the case? I get confuse since in making productions for ...
4
votes
1answer
53 views

How to use Parikh's Theorem to show language is not context free

Parikh's Theorem is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, ...
0
votes
0answers
33 views

Pumping Lemma to prove that L is not context free

I have the language and I want to prove that is not context-free. So I started like this: is variable. Choose w = Case 1: vxy has no c. Choose i = 2 has more a than c or more b than c. Case 2: ...
0
votes
2answers
30 views

Proof for TM accepting any PDA-language

How do you suggest I go about proving this: Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing ...
0
votes
1answer
57 views

How to prove {a^(n^2) | n>0} is not context-free?

So I have a language: $$ L = \{a^{n^2} \mid n > 0\} $$ I need to prove that this language isn't context-free using the pumping lemma. I have a vague thought process as to how to do the proof but ...
13
votes
1answer
299 views

Is language equality for linear context-free grammars decidable?

Let's consider two context-free grammars $G_1$ and $G_2$ and ask the following question: Is $L(G_1) = L(G_2)$, that is, are the two grammars equivalent? In general, this problem is undecidable. ...
4
votes
2answers
468 views

Does a context-free grammar with multiple variables have a “starting” point?

So lets consider the following grammar $$ \begin{align*} S &\to 0 \mid 0A \\ A &\to 1 \end{align*} $$ would the string "1" be accepted by the language or must the language start with $S$?
2
votes
1answer
92 views

How to use a CFG to restrict a subset of a*b*c*d* so that there are at most as many a's and b's as d's?

Give Context-free Grammar for the language $\{a^i b^j c^k d^h \mid i,j,h \ge 0, k>0, i+j \le h\}$ This is a training exercise, for which we don't get any answers, in a course I'm taking. I ...
1
vote
1answer
68 views

Can every context free grammar be transformed into equivalent grammar of this form?

Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where $a \in V_t$ and $A,B,C \in V_n $ with rewriting rules of ...
-3
votes
0answers
22 views

How to prove a language is not context free using pumping lemma? [duplicate]

So I have a question in particular here, I need to prove that the following is not context free: $\{0^m1^n0^m1^n | m,n \in \mathbb{N} \}$ I am fully aware that I need to use the pumping lemma for ...
0
votes
1answer
35 views

Context free Grammar and regular set

I read a question and I don't understand it, is the set consisting of: production rules of Grammars that are CFGs, itself a regular set? The only thing I know is that the type 3 is under the type 2 in ...
0
votes
1answer
44 views

Showing a language is context free. Use PDA or CFG?

I am wondering on how to approach a specific problem I am struggling with. I am not understanding which way to approach it and how to solve it. Show language $L$ is context free, where $L = ...
0
votes
1answer
28 views

Why descriptive power of context-free grammar is greater than regular expression?

Below is a saying from this article. Regular expressions sit just beneath context-free grammars in descriptive power: you could rewrite any regular expression into a grammar that represents the ...
1
vote
1answer
23 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
-4
votes
0answers
21 views

Context-free languages [duplicate]

What does the proof look like for this question?
1
vote
0answers
10 views

How can we avoid mistake in LL(1) parse tree?

I'm learning about LL(1) parse tree. We need to find first and follow in order to construct a LL(1) parse tree. Each and every ...
0
votes
1answer
44 views

If the strings of a language can be enumerated in lexicographic order, is it recursive?

If the strings of a language L can be effectively enumerated in lexicographic order then is the statement "L is recursive but not necessarily context free" is true?
0
votes
1answer
35 views

Determine whether a context-free language is deterministic or not

I define language $L = \{a^k a^m b^m c^k \} \cup \{a^n b^n b^k c^k\}$ and I want to determine if it's deterministic context free language or it is nondeterministic. so I tried to create pushdown ...
0
votes
3answers
84 views

What is the language generated by a given grammar

Given the grammar $s \to aSb \mid bSb \mid a \mid b$; what is the language generated by the grammar over the alphabet $\{a,b\}$? When I was solving this question I was a bit confused about ...
-3
votes
1answer
42 views

CFG for the language “number of a's = number of b's + 2”

How can I construct a context-free grammar for the following language? $$ L = \{ w \in \{a,b\}^* : \#_a(w) = \#_b(w) + 2 \}. $$ Please help me out in this. I am not sure how to approach this ...
1
vote
1answer
16 views

What is the complement of the language with all ucv with u ≠ v?

If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he ...
-3
votes
1answer
28 views

clarification about first for cfg [closed]

S-->ABCDE A-->a/ε B-->b/ε C-->c D-->d/ε E-->e/ε i have solved first for above question but a little clarification is required first(S)= first(A)=a/ε first(B)=b/ε first(C)=c first(D)=d/ε ...
0
votes
1answer
29 views

removing ε production

It's not that i dont know how to remove εproduction but when complex problem arises i get confused for example S-->Aa/aaB A-->a/ε B-->bbA/ε CFG without ε production for the above question is ...
-1
votes
1answer
26 views

Need help removing ambiguity from grammar

$E \rightarrow UV \bracevert EBE \bracevert V \bracevert [E]$ $V \rightarrow a \bracevert b$ $U \rightarrow < \bracevert > $ $B \rightarrow ? \bracevert ! \bracevert @ $ Order of precedence: ...
3
votes
2answers
47 views

Meta-grammar for context-free grammars

Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet. Grammars themselves can be seen as languages, e.g. the set of ...
-3
votes
1answer
48 views

Finding the language generated for CFG

What language generated by the following context-free grammar 1) S------> SaS | b i already know the answer to question one but to prove it would is be something like this: S -----> SaaS -----> baab ...
1
vote
0answers
25 views

Decidability Proof of $A_{Cfg}$

I am a beginner to complexity theory and I came up with the following proof of decidability of $A_{Cfg}$ = {$<G,w>|G$ is a context free grammar that generates string $w$} The Turing machine ...
-4
votes
2answers
83 views

odd length palindrome's f=language [closed]

Find the language generated by the following grammar over the input alphabet = {a,b}. S –> aSa | bSb | a | b The language generated by the above grammar over the alphabet {a,b} is the set of (A) ...
0
votes
0answers
41 views

Proof of completeness for CFG having twice as many zeroes as ones [duplicate]

One possible CFG containing twice as many zeros as ones can be, S -> 0S0S1S | 0S1S0S | 1S0S0S | ϵ (This CFG is redundant but it will do the job. So I am not interested in the redundancy. Other ...
0
votes
1answer
26 views

How to choose symbols to replace for this left-most derivation?

I have a context free grammar such as the following: $E→E+T | T$ $T→T×F | F$ $F→(E) | a$ Using the left-most derivation, the following can be derived: $E⇒E+T⇒T+T⇒F+T⇒a+T$ $⇒a+F⇒a+(E)⇒a+(T)$ ...
1
vote
1answer
82 views

Why do we not use CFGs to describe the structure of lexical tokens?

This was an exam question for my course and I am struggling to actually answer it in a way that is not fluff. Here is my current answer: CFGs describe how non-terminal symbols are converted into ...
0
votes
2answers
65 views

Context free grammar for nested arrays separated by commas

I have to define a context free grammar for the following rules: (i) A pair of square bracket tokens [] surrounding zero or more values separated by commas. (ii) A value can be another array or a ...
2
votes
1answer
95 views

Proving that the scramble of a regular language is context-free

For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator ...
0
votes
1answer
38 views

Prove using pumping free lemma for context-free languages

One of the exercises I tried to make I failed miserably. The question was as follows: Show that the language $L = \{ w \,|\, n_a(w) \cdot n_b(w) = n_c(w) \}$ is not context-free. (with $n_a(w)$ ...
4
votes
1answer
57 views

Closure properties of the class of inherently ambiguous CFLs

is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are ...
3
votes
2answers
71 views

Why are palindrome and not-palindrome both context-free?

Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two ...
4
votes
1answer
57 views

Is it decidable whether a linear language contains a square?

A square is a word of the form $ww$. A linear grammar is a CFG that has productions of the form $A\to uBv$ or $A\to u$ (with lower case symbols corresponding to terminal strings). Question: Is it ...
0
votes
1answer
42 views

Characterizing a CFG equivalent to a special type of PDA

Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which ...
3
votes
0answers
55 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
4
votes
3answers
279 views

Is the set of CFGs that contain all odd and even length words Turing-decidable?

$ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)} $ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd ...
0
votes
2answers
30 views

Different between Left most and Right most derivation [duplicate]

I am a beginner started learning theoretical computer science.. I just came through. "Context free grammar" So my Question is that what is the different between Left most and Right most derivation. ...
1
vote
2answers
68 views

Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?

Consider the language $L \subseteq \{a,b,c\}^*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a ...
-2
votes
2answers
90 views

Why do grammars in Chomsky Normal Form have derivations of length 2n-1?

I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3): The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters ...
-1
votes
2answers
51 views

Design a grammar for this context-free language

I am doing an exercise from Models Of Computation - Ch - 5, Q-1(r). Design a grammar that generates this context-free language $\{ x\space\$\space y^R \,|\, x, y \in\{0, 1\}^* \text{ and } x \ne ...
0
votes
0answers
20 views

What is the complement of this Context-Free Language? [duplicate]

$L = \{ a^i b^i c^i | i \ge 0 \}$ I understand that it's everything not in $L$, so every string where $\#a's = \#b's = \#c's$ is not in $L$ complement. However, I wasn't sure if strings such as $ba$ ...