# Recent questions tagged context-free-grammars

1
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ {$a^nb^mc^k : n + 2m = k$}. (e) $L =$ ... $a, b, c$}$^* : n_a (w) + n_b (w) ≠ n_c (w)$}. (g) $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
2
Find context-free grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$}. (c) https://gateoverflow.in/208410/peter-linz-edition-4-exercise-5-1-question-7-c-page-no-133 (d) $L =$ {$a^nb^m : 2n ≤ m ≤ 3n$ ... $^* : n_a (v) ≥ n_b (v),$ where $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
3
Give the Complete proof of Theorem 5.1 by showing that the yield of every partial derivation tree with root $S$ is a sentential form of $G$. Theorem 5.1 Let $G = (V, T, S, P )$ be a context-free grammar. Then for every $w ∈ L (G)$, there exists a derivation tree ... , if $t_G$ is any partial derivation tree for $G$ whose root is labeled $S$, then the yield of $t_G$ is a sentential form of $G$.
4
Show that the grammar with productions $S\rightarrow aSb|SS|\lambda$ does in fact generate the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)=n_b(w)$ and $n_a(v)\geq n_b(v),$ where $v$ is any prefix of $w$}.
1 vote
5
Give a derivation tree for $w = abbbaabbaba$ for the grammar $G$, with productions $S\rightarrow abB$ $A\rightarrow aaBb$ $B\rightarrow bbAa$ $A\rightarrow \lambda$. Use the derivation tree to find a leftmost derivation.
6
Draw the derivation tree corresponding to the derivation in Example 5.1. Example 5.1 The grammar $G = (${$S$}, {$a, b$}$, S, P),$ with productions $S\rightarrow aSa$ $S\rightarrow bSb$ $S\rightarrow \lambda$ is context-free. A typical derivation in this grammar is $S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabbaa.$
7
Find the language generated by following grammar: The grammar G, with productions $S\rightarrow abB$ $A\rightarrow aaBb$ $B\rightarrow bbAa$ $A\rightarrow \lambda$
8
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
9
Show that in any $CNF$ grammar all parse trees for strings of length $n$ have $2n-1$ interior nodes $(i.e.,$ $2n-1$ nodes with variables for lables$).$
10
Using the grammar $G$ of Example $7.34,$use the $CYK$ algorithm to determine whether each of the following strings is in $L(G):$ $ababa$ $baaab$ $aabab$
11
Use the technique described in Section $7.4.3$ to develop linear time algorithms for the following questions about $CFG's:$ Which symbols appear in some sentential form$?$ Which symbols are nullable $\text{(derive$\in$)?}$
12
Use the construction of question $11$ to convert the grammar $S\rightarrow AA|0$ $A\rightarrow SS|1$ to $GNF.$
13
In this exercise, we shall show that for every context-free language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that generates $L-\in.$ Recall that a Greibach normal form $(GNF)$ grammar is one where every production body starts with a terminal. ... $,$ down to $A_{1}$ using part $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$
14
Is it possible to find, for every context-free language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body consisting of three variables$),$ or $A\rightarrow a$ $($i.e., a body consisting of a single terminal$)?$ Give either a proof or a counterexample.
15
Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating. Both directions of Theorem $7.6$ where we show the correctness of the algorithm in Section $7.1.2$ for detecting the reachable symbols. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.
16
Let $G$ be an $\in-$production-free grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$ Show that the CNF grammar has at most $O(n^{2})$ productions. Show that it is possible for the $CNF$ grammar to have a number of productions proportional to $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.
17
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}-1)}{(n-1)}$ steps. How close can you actually come to this bound$?$
18
Design a CNF grammar for the set of strings of balanced parentheses.You need not start from any particular non-CNF grammar.
19
Begin with the grammar$:$ $S\rightarrow aAa|bBb|\in$ $A\rightarrow C|a$ $B\rightarrow C|b$ $C\rightarrow CDE|\in$ $D\rightarrow A|B|ab$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
20
Begin with the grammar$:$ $S\rightarrow AAA|B$ $A\rightarrow aA|B$ $B\rightarrow \in$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
21
Begin with the grammar$:$ $S\rightarrow 0A0|1B1|BB$ $A\rightarrow C$ $B\rightarrow S|A$ $C\rightarrow S|\in$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
22
Begin with grammar$:$ $S\rightarrow ASB|\in$ $A\rightarrow aAS|a$ $B\rightarrow SbS|A|bb$ Eliminate $\in-$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
23
Find a grammar equivalent to $S\rightarrow AB|CA$ $A\rightarrow a$ $B\rightarrow BC|AB$ $C\rightarrow aB|b$ with no useless symbols.
24
For each of the following PDA's, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it. $a)$ $b)$ Suppose the $PDA,$ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ has the following transition function$:$ ... $\delta(q,\in,X)=\{(q,\in)\}$ $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
25
Suppose we have a PDA with $s$ states $t$ stack symbols and no rule in which a replacement stack string has a length greater than $u.$ Give a tight upper bound on the number of variables in the $CFG$ that we construct for this PDA by the method of an empty stack.
26
Below are some context-free languages.For each,devise a PDA that accepts the language by empty stack. You may ,if you wish, first construct a grammar for the language, and then convert to a $PDA:$ $\{a^{n}b^{m}c^{2(n+m)}|n\geq 0,m\geq 0\}$ $\{a^{i}b^{j}c^{k}|i=2j$(or)$j=2k\}$ $\{0^{n}1^{m}|n\leq m\leq 2n\}$
27
Convert the $PDA,$ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ to a $CFG,$ if $\delta$ given by $:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ $\delta(q,\in,X)=\{p,\in\}$ $\delta(p,\in,X)=\{p,\in\}$ $\delta(p,1,X)=\{(p,XX)\}$ $\delta(p,1,Z_{0})=\{p,\in\}$
Convert the $PDA$ $P=(\{p,q\},\{0,1\},\{X,Z_{0}\},\delta.q.Z_{0})$ to a $CFG,$ if $\delta$ is given by $:$ $\delta(q,1,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,1,X)=\{(q,XX)\}$ $\delta(q,0,X)=\{(p,X)\}$ $\delta(q,\in,X)=\{(q,\in)\}$ $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
The following grammar generates prefix expressions with operands $x$ and $y$ and binary operators $+,-$ and $*$ $:$ $E\rightarrow +EE|*EE|-EE|x|y$ Find leftmost and rightmost derivations and a derivation tree for the string $+*-xyxy.$ Prove that this grammar is unambiguous.
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$ Is your grammar is unambiguous$?$ If not,redesign it to be unambiguous.