search
Log In

Recent questions tagged context-free-grammars

0 votes
0 answers
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$}.
asked Apr 13, 2019 in Theory of Computation Naveen Kumar 3 58 views
0 votes
0 answers
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$}.
asked Apr 13, 2019 in Theory of Computation Naveen Kumar 3 98 views
0 votes
0 answers
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$.
asked Apr 13, 2019 in Theory of Computation Naveen Kumar 3 27 views
0 votes
0 answers
4
1 vote
0 answers
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.
asked Apr 13, 2019 in Theory of Computation Naveen Kumar 3 32 views
0 votes
0 answers
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.$
asked Apr 13, 2019 in Theory of Computation Naveen Kumar 3 48 views
0 votes
0 answers
7
0 votes
0 answers
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$)?}$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
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).$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 15 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 18 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 31 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 53 views
0 votes
0 answers
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$?$
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 36 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 28 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 53 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 14 views
0 votes
0 answers
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.
asked Apr 11, 2019 in Theory of Computation Lakshman Patel RJIT 19 views
0 votes
1 answer
23
0 votes
0 answers
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})\}$
asked Apr 7, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
0 votes
0 answers
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.
asked Apr 7, 2019 in Theory of Computation Lakshman Patel RJIT 66 views
0 votes
0 answers
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\}$
asked Apr 7, 2019 in Theory of Computation Lakshman Patel RJIT 59 views
0 votes
0 answers
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\}$
asked Apr 7, 2019 in Theory of Computation Lakshman Patel RJIT 23 views
0 votes
0 answers
28
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})\}$
asked Apr 7, 2019 in Theory of Computation Lakshman Patel RJIT 26 views
0 votes
0 answers
29
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.
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 78 views
0 votes
0 answers
30
...