Register

Recent questions tagged context-free-grammar

324
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 6 (Page No. 216)
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.
User Avatar
241
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 5 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A|\in$ $B\rightarrow 0B|1B\in$Show that this grammar is unambiguous.Find a grammar for the same language that is ambiguous and demonstrate its ambiguity.
User Avatar
247
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 4 (Page No. 216)
Some strings of $a's$ and $b's$ have a unique parse tree in the grammar of $S\rightarrow aS|aSbS|\in.$ Give an efficient test to tell whether a given ... parse trees to see how many yield the given string$"$ is not adequately efficient$.$
User Avatar
247
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 3 (Page No. 216)
Find an unambiguous grammar for the language of $S\rightarrow aS|aSbS|\in$
User Avatar
213
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 2 (Page No. 216)
Prove that the grammar generates all only the strings of $a's$ and $b's$ such that every prefix has at least as many $a's$ as $b's.$ $S\rightarrow aS|aSbS|\in$
User Avatar
167
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.4 Question 1 (Page No. 215)
Consider the grammar $S\rightarrow aS|aSbS|\in$This grammar is ambiguous. Show in particular that the string $aab$ has two$:$Parse treesLeftmost derivationsRightmost derivations
User Avatar
158
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.2 Question 4 (Page No. 193)
If $X_{1}X_{2}.....X_{k}\overset{*}\Rightarrow \alpha,$ then all the positions of $\alpha$ that come from expansion of $X_{i}$ are to the left of ... this fact$.$ Hint$:$ Perform an induction on the number of steps in the derivation$.$
User Avatar
354
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.2 Question 3 (Page No. 193)
Suppose all is as in question $2,$ but $G$ may have some productions with $\in$ as the right side. Show that a parse tree for a string $w$ other than $\in$ may have as many as $n+2m-1$ nodes,but no more.
User Avatar
190
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.2 Question 2 (Page No. 193)
Suppose that $G$ is a $CFG$ without any productions that have $\in$ as the right side. If $w$ is in $L(G),$ the length of $w$ is $n$ and $w$ has a derivation of $m$ steps, show that $w$ has a parse tree with $n+m$ nodes.
User Avatar
140
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.2 Question 1 (Page No. 193)
For the following grammar and each of the strings gives pase trees.$S\rightarrow A1B$A\rightarrow 0A|\in$B\rightarrow B|1B|\in$00101$ $1001$ $00011$
User Avatar
1.4k
views
1 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 8 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$S\rightarrow aSbS|bSaS|\in$Prove that $L(G)$ is the set of all strings with an equal number of $a's$ and $b's.$
User Avatar
2.0k
views
1 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 7 (Page No. 183)
Consider the CFG $G$ defi ned by productions$:$S\rightarrow aS|Sb|a|b$Prove by induction on the string length that no string in $L(G)$ has $ba$ as a substring.Describe $L(G)$ informally. Justify your answer using part $(a).$
User Avatar
242
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 6 (Page No. 182 - 183)
We defined the relation $\overset{*}\Rightarrow$ with a basis $"\alpha\Rightarrow \alpha $ and an induction that says $\alpha\overset{*}\Rightarrow\beta$ and ... on the number of steps in the derivation $\beta\overset{*}\Rightarrow\gamma.$
User Avatar
272
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 5 (Page No. 182)
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only ... with set of terminals $T$ that generates exactly the regular expressions with alphabet $\{0,1\}.$
User Avatar
384
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 4 (Page No. 182)
A CFG is said to be right-linear if each production body has at most one variable and that variable is at the right end. That is all productions of a right ... . Hint$:$Start with a DFA and let the variables of the grammar represent states.
User Avatar
282
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 2 (Page No. 182)
The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$S\rightarrow A1B$A\rightarrow 0A|\in$B\rightarrow B|1B|\in$Give leftmost and rightmost derivations of the following strings$:$00101$ $1001$ $00011$
User Avatar
332
views
0 answers
0 votes
Ullman (TOC) Edition 3 Exercise 5.1 Question 1 (Page No. 181 - 182)
Design context-free grammars for the following languages$:$The set $\{0^{n}1^{n}|n\geq 1,\}$that is the set of all strings of one or more $0's$ followed by ... any string repeated.The set of all strings with twice as many $0's$ as $1's.$
User Avatar
648
views
0 answers
0 votes
Ullman(Second Edition) Exercise 4.2.3. Question (a) (page no-207)
Design grammar for the language-set of all strings of 0s and 1s such that every 0 is immediately followed by at least one 1 is this correct?S->A | 01SA->1AS | ε
User Avatar
494
views
1 answers
1 votes
Ullman Exercise
What language is generated by the following grammer?S→ a | S+S | SS | S* | (S)
User Avatar
413
views
1 answers
0 votes
No of strings of fixed length possible with a given grammar
What is the number of terminal string of length <= 6 generated by the CFG shown below?S -> 0A1A -> BB1/BB ->A/0/1Do you have any semantic method to solve ... but I am wondering what if it had been asked no of strings of length n Thanks
User Avatar
889
views
1 answers
1 votes
CFG Doubt
what is the CFG for the language L=w where number of a’s in w+number of b’s in w=number of c’s in whow to approach this?
User Avatar
911
views
1 answers
0 votes
CFG Doubt
S->A | BA→ εB->aBbB->bwhat is the complement of the language of this grammar?
User Avatar
453
views
1 answers
0 votes
Peter Linz Edition 4 Exercise 5.1 Question 13.a (Page No. 134)
L={$a^nb^n | n\geq 0$}please show how $L^2$ is CFL
User Avatar
969
views
1 answers
0 votes
#ComplierDesign #DragonsBook
For any context-free grammar there is a parser that takes at most O (n$^3$ )time to parse a string of n terminals.True or False?
User Avatar
729
views
1 answers
0 votes
ACE Test series Question on CFG
User Avatar
1.7k
views
1 answers
0 votes
Ace Test Series: Compiler Design - Left Recursion Elimination
User Avatar
309
views
1 answers
1 votes
ME TEST Series question ON CFG
User Avatar
1.1k
views
1 answers
1 votes
Applied Course | Mock GATE | Test 1 | Question: 13
Which of the following statement is not correct?$a^nb^nc^m$ is not CFG$a^mb^nc^n$ is deterministic CFG$a^nb^n$ is CFG$a^{800}b^{800}c^{800}$ is CFG
User Avatar
745
views
1 answers
1 votes
Applied Course | Mock GATE | Test 1 | Question: 60
The left-factoring of the given CFG is$S \rightarrow aBcD \mid aBD \mid daB \mid d$B \rightarrow b$D \rightarrow d$ ... dB' \mid d$B' \rightarrow aB$B \rightarrow b$D \rightarrow d$None of them
User Avatar
398
views
1 answers
0 votes
UPPCL AE 2018:64
The following grammar $\text{G}$ is left recursive.$\text{E} \rightarrow \text{E + T}\; \mid \; \text{T} $\text{T} \rightarrow \text{T * F} \; \mid \; \text{F ...
User Avatar
Page: