Recent questions tagged context-free-grammars

0 votes

0 answers

1

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 10 (Page No. 233)
Show how, having filled in the table as in Question $4.4.9$, we can in $O(n)$ time recover a parse tree for $a_{1}a_{2}\cdot\cdot\cdot a_{n}$. Hint: modify the table so it records, for each nonterminal $A$ in each table entry $T_{ij}$, some pair of nonterminals in other table entries that justified putting $A$ in $T_{ij}$.

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

2

Ullman (Compiler Design) Edition 2 Exercise 4.4 Question 9 (Page No. 232)
Every language that has a context-free grammar can be recognized in at most $O(n^{3})$ time for strings of length $n$. A simple way to do so,called the Cocke- Younger-Kasami (or CYK) algorithm is based on dynamic programming. ... a_{l}a_{2}\cdot\cdot\cdot a_{n} is in the language?

asked 4 days ago in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

3

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 3 (Page No. 207)
Design grammars for the following languages: The set of all strings of $0's$ and $1's$ such that every $0$ is immediately followed by at least one $1$. The set of all strings of $0's$ and $1's$ that are palindromes; that is, the string ... $1's$ of the form $xy$, where $x\neq y$ and $x$ and $y$ are of the same length.

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

4

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 2 (Page No. 206 - 207)
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$ ... $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$

asked Aug 17 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 5 views

0 votes

1 answer

5

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 1 (Page No. 206)
Consider the context-free grammar:$S\rightarrow SS + \mid SS {\ast} \mid a$and the string $aa + a{\ast}$. Give a leftmost derivation for the string. Give a rightmost derivation for the string. ... for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.

asked Aug 7 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 28 views

0 votes

0 answers

6

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 6 (Page No. 52)
Construct a context-free grammar for roman numerals.

asked Jul 26 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 2 views

0 votes

0 answers

7

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 4 (Page No. 51 - 52)
Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct. Arithmetic expressions in postfix notation. Left-associative lists of identifiers separated by commas. Right- ... $(d)$.

asked Jul 26 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 5 views

+1 vote

2 answers

8

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 3 (Page No. 51)
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$

asked Jul 26 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 17 views

0 votes

0 answers

9

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 2 (Page No. 51)
What language is generated by the following grammars? In each case justify your answer. $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$

asked Jul 26 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 3 views

0 votes

0 answers

10

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 1 (Page No. 51)
Consider the context-free grammar $S\rightarrow SS+\mid SS^{\ast}\mid a$ Show how the string $aa+a^{\ast}$ can be generated by this grammar. Construct a parse tree for this string. What language does this grammar generate? Justify your answer.

asked Jul 26 in Compiler Design by Lakshman Patel RJIT Boss (45.8k points) | 1 view

0 votes

0 answers

11

Ullman (TOC) Edition 3 Exercise 9.5 Question 1 (Page No. 418)
Let $L$ be the set of (codes for) context-free grammars $G$ such that $L(G)$ contains at least one palindrome. Show that $L$ is undecidable. Hint: Reduce PCP to $L$ by constructing, from each instance of PCP a grammar whose language contains a palindrome if and only if the PCP instance has a solution.

asked Jul 26 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 4 views

0 votes

0 answers

12

Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 16 views

0 votes

0 answers

13

Peter Linz Edition 4 Exercise 7.4 Question 8 (Page No. 204)
Let G be a context-free grammar in Greibach normal form. Describe an algorithm which, for any given k, determines whether or not G is an LL (k) grammar.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 11 views

0 votes

0 answers

14

Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

15

Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

16

Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

17

Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 5 views

0 votes

0 answers

18

Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 7 views

0 votes

0 answers

19

Peter Linz Edition 4 Exercise 7.4 Question 1 (Page No. 204)
Show that the grammar $S_0\rightarrow aSbS,S\rightarrow aSbS|\lambda$ is an LL grammar and that it is equivalent to the grammar $S\rightarrow SS|aSb|ab$.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14k points) | 8 views

+1 vote

1 answer

20

ISI2018-PCB-B4
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s = UUDU$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person is initially ... returns to the base of the staircase after the final step. Show that $L$ is not regular Write a context free grammar for accepting $L$

asked May 12 in Theory of Computation by akash.dinkar12 Boss (41.3k points) | 28 views

0 votes

1 answer

21

Michael Sipser Edition 3 Exercise 2 Question 28 (Page No. 157)
Give unambiguous $CFG's$ for the following languages$.$ $\text{{$w\mid$ in every prefix of $w$ the number of $a’s$ is at least the number of $b’s$}}$ $\text{{$w\mid$ the number of $a’s$ and the number of $b’s$ in $w$ are equal}}$ $\text{{$w\mid$ the number of $a’s$ is at least the number of $b’s$ in $w$}}$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 22 views

0 votes

1 answer

22

Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a natural-looking grammar for a fragment of a programming language, but $G$ is ambiguous$.$ Show that $G$ is ambiguous$.$ Give a new unambiguous grammar for the same language$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 20 views

+1 vote

1 answer

23

Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 23 views

0 votes

1 answer

24

Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 22 views

0 votes

1 answer

25

Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 9 views

0 votes

0 answers

26

Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)
Let $CFG$ $G$ be the following grammar$.$ $S\rightarrow aSb \mid bY \mid Y a$ $Y\rightarrow bY \mid aY \mid \epsilon$ Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 10 views

0 votes

0 answers

27

Michael Sipser Edition 3 Exercise 2 Question 15 (Page No. 156)
Give a counterexample to show that the following construction fails to prove that the class of context-free languages is closed under star. Let $A$ be a $\text{CFL}$ that is generated by the $\text{CFG}$ ... new rule $S\rightarrow SS$ and call the resulting grammar $G'.$This grammar is supposed to generate $A^{*}.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 12 views

0 votes

1 answer

28

Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 20 views

0 votes

1 answer

29

Michael Sipser Edition 3 Exercise 2 Question 13 (Page No. 156)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ $U\rightarrow 0U00\mid\#$ Describe $L(G)$ in English. Prove that $L(G)$ is not regular$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 22 views

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 2 Question 12 (Page No. 156)
Convert the $CFG$ $G$ $R\rightarrow XRX \mid S$ $S\rightarrow aT b \mid bT a$ $T\rightarrow XT X \mid X \mid\epsilon$ $X\rightarrow a \mid b$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$

asked May 2 in Theory of Computation by Lakshman Patel RJIT Boss (45.8k points) | 19 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged context-free-grammars

Recent Posts

Recent Blog Comments