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
votes
0answers
6 views

Recursion Type in Grammar Productions

The grammar G0 is defined by the productions P= xP|y which type of recursion is it left , central , right or indirect recursion
1
vote
0answers
7 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
35 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
28 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
74 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
32 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
13 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

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
43 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
44 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
20 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
61 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
31 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
25 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
37 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
1answer
36 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
84 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
29 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
66 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 ...
-1
votes
0answers
25 views

If a CFG has a word with length more than its variables then the language of it is infinite?

Grammar G have n variables in normal Chomsky form, It can build a word with length w, using m rules. Which disprove each of following statements: If w > n then the language of the grammar G is ...
4
votes
1answer
55 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
41 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
53 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
273 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
19 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
49 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
19 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$ ...
0
votes
1answer
34 views

Pushdown Automata: How can I recognize a ratio threshold between two symbols in a string?

I'm trying to design a pushdown automata where there are two symbols in the alphabet and the accept state is when there is >= 60% of symbol A. I'm trying to think in terms of what to save on the ...
0
votes
2answers
52 views

Showing that a language satisfies the pumping lemma

I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma If L = {ambncndn | m,n >= 1 } Should I have n be the constant of the ...
0
votes
1answer
41 views

Converting context-free grammar to Chomsky/Greibach Normal Form

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). ...
5
votes
2answers
658 views

In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree. So, my question is: Why is it ...
-1
votes
1answer
65 views

Need to give a CFG for this language?

I have the language: $$ L = \{0^m1^n \mid 0 ≤ m ≤ n\text{ or }0 ≤ n ≤ 2m\}. $$ My goal is to give an equivalent context-free grammar for this language, but I am unsure if I am going about it the ...
0
votes
1answer
36 views

If a language is context free, then its complement is decidable

I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore ...
-1
votes
1answer
66 views

Converting a language to a PDA?

I am trying to convert the follow language $$L = \{0^m1^n \ | \ 0 \le m \le n \le 2m\}$$ We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though ...
2
votes
2answers
52 views

Proving a CFG is ambiguous?

I have a CFG: S --> 0S1S | 1S0S | ε I'm trying to prove that it is ambiguous, but the steps to proving so are confusing me. So if I pick a string, let's say ...
0
votes
0answers
21 views

Parsing text in two dimensions

I would like to define grammar rules which define how a token is related not only to the left and to the right (as in usual stream of characters that parses deal with), but also to the top and to the ...
-2
votes
2answers
136 views

How is $a^nb^nc^{2n}$ not a context free language, where as $a^nb^mc^{n+m}$ is? [duplicate]

$L_1 = \{a^mb^nc^{m+n}: n,m>1\}$ I know $L_1$ is CFL and works with a pushdown automata. $L_2 = \{a^nb^nc^{2n}: n>1\}$ The language $L_2$ should also be a CFL because it looks similar, but ...
0
votes
1answer
37 views

How is CFL-reachability solvable in exponential time and space?

I have read a paper which mentions that CFL-reachability is solvable in exponential time and space. Intuitively, I suppose that one need to explore through all the sub-paths in the PDA for a CFL. ...
0
votes
1answer
28 views

Writing context free grammar

I have the following language: {0m1n0n1m | m,n ≠ 0} I was wanting to write Context-free grammar for it. I'm a little confused because the rule doesn't mention that m and n are not equal to each ...
1
vote
0answers
25 views

Modifying the grammar to include another operator

I have this grammar for arithmetic expressions E -> E+T | T T -> T X F | F (X is cross product operator) F -> (E) | a Now I am wanting to add the exponential operator ^ to it, it needs to ...
1
vote
1answer
42 views

Proof that the set of all universal CFGs is co-RE complete

Let $\Sigma^*\text{CFL} = \{G \mid G \text{ is a CFG; } L(G) = \Sigma_G^*\}$. Enumerate the r.e. sets by $W_n$. Let $\text{EMPTY}= \{ n \mid W_n=\emptyset\}$. On page 4 of these lecture notes, to ...
3
votes
1answer
63 views

Can I remove left recursion on this grammar

$S \rightarrow Sa \mid S \mid \epsilon$ This is a weird case where I have only one non-terminal. I'm trying to apply the algorithm 4.19 in the dragon book. It don't think it should be applicable but ...
0
votes
0answers
28 views

Eliminating left recursion and left factoring this grammar

I have a grammar S-> SS* | SS+ | a Really confused on how to remove the left recursion and do left factoring My attempt on removing left recursion : S -> aS' S' -> S+S' | S*S' | epsilon If this is ...
0
votes
0answers
24 views

How can I extend a context-free grammar to Lexical semantics?

Here it was suggested that I may need Lexical semantics for my parsing problems. How can I extend a context-free grammar to Lexical semantics? I've thought attribute grammars already, but they seem ...
2
votes
1answer
32 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 ...