Recent questions tagged context-free-grammars - GATE Overflow

0 votes

0 answers

1

Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 40 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 5 Question 32 (Page No. 241)
Prove that the following two languages are undecidable. $OVERLAP_{CFG} = \{\langle G, H\rangle \mid \text{G and H are CFGs where}\: L(G) \cap L(H) \neq \emptyset\}$. $PREFIX-FREE_{CFG} = \{\langle G \rangle \mid \text{G is a CFG where L(G) is prefix-free}\}$.

asked Oct 20 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 5 views

0 votes

0 answers

3

Michael Sipser Edition 3 Exercise 5 Question 21 (Page No. 240)
Let $AMBIG_{CFG} = \{\langle G \rangle \mid \text{G is an ambiguous CFG}\}$. Show that $AMBIG_{CFG}$ is undecidable. (Hint: Use a reduction from $PCP$ ... $a_{1},\dots,a_{k}$ are new terminal symbols. Prove that this reduction works.)

asked Oct 19 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 2 views

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is co-Turing-recognizable.

asked Oct 17 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 10 views

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 5 Question 1 (Page No. 239)
Show that $EQ_{CFG}$ is undecidable.

asked Oct 17 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 4 views

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 4 Question 31 (Page No. 212)
Say that a variable $A$ in $CFL\: G$ is usable if it appears in some derivation of some string $w \in G$. Given a $CFG\: G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.

asked Oct 17 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 4 views

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 4 Question 29 (Page No. 212)
Let $C_{CFG} = \{\langle G, k \rangle \mid \text{ G is a CFG and L(G) contains exactly $k$ strings where $k \geq 0$ or $k = \infty$}\}$. Show that $C_{CFG}$ is decidable.

asked Oct 17 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 5 views

0 votes

0 answers

8

Michael Sipser Edition 3 Exercise 4 Question 28 (Page No. 212)
Let $C = \{ \langle G, x \rangle \mid \text{G is a CFG $x$ is a substring of some $y \in L(G)$}\}$. Show that $C$ is decidable. (Hint: An elegant solution to this problem uses the decider for $E_{CFG}$.)

asked Oct 17 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 5 views

0 votes

0 answers

9

Michael Sipser Edition 3 Exercise 2 Question 59 (Page No. 160)
If we disallow $\epsilon$-rules in CFGs, we can simplify the DK-test. In the simplified test,we only need to check that each of DK’s accept states has a single rule. Prove that a CFG without $\epsilon$-rules passes the simplified DK-test iff it is a DCFG.

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 4 views

0 votes

0 answers

10

Michael Sipser Edition 3 Exercise 2 Question 55 (Page No. 159)
Let $G_{1}$ be the following grammar that we introduced in Example $2.45$. Use the DK-test to show that $G_{1}$ is not a DCFG. $R \rightarrow S \mid T$ $S \rightarrow aSb \mid ab$ $T \rightarrow aTbb \mid abb$

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 4 views

0 votes

0 answers

11

Michael Sipser Edition 3 Exercise 2 Question 54 (Page No. 159)
Let G be the following grammar: $S \rightarrow T\dashv $ $T \rightarrow T aT b \mid T bT a | \epsilon$ Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers of a’s and b’s} \}$. Use a proof by induction on the length of $w$. Use the DK-test to show that G is a DCFG. Describe a DPDA that recognizes L(G).

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 4 views

0 votes

0 answers

12

Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)
Show that every DCFG generates a prefix-free language.

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 5 views

0 votes

0 answers

13

Michael Sipser Edition 3 Exercise 2 Question 51 (Page No. 159)
Show that every DCFG is an unambiguous CFG.

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 3 views

0 votes

0 answers

14

Michael Sipser Edition 3 Exercise 2 Question 47 (Page No. 159)
Let $\Sigma = \{0,1\}$ and let $B$ be the collection of strings that contain at least one $1$ in their second half. In other words, $B = \{uv \mid u \in \Sigma^{\ast}, v \in \Sigma^{\ast}1\Sigma^{\ast}\: \text{and} \mid u \mid \geq \mid v \mid \}$. Give a PDA that recognizes $B$. Give a CFG that generates $B$.

asked Oct 13 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 8 views

0 votes

0 answers

15

Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.

asked Oct 12 in Theory of Computation by Lakshman Patel RJIT Veteran (52.9k points) | 6 views

0 votes

0 answers

16

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (52.9k points) | 2 views

0 votes

0 answers

17

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 Aug 20 in Compiler Design by Lakshman Patel RJIT Veteran (52.9k points) | 3 views

0 votes

0 answers

18

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 Veteran (52.9k points) | 4 views

0 votes

0 answers

19

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 Veteran (52.9k points) | 10 views

0 votes

1 answer

20

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 Veteran (52.9k points) | 41 views

0 votes

0 answers

21

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 Veteran (52.9k points) | 4 views

0 votes

0 answers

22

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 Veteran (52.9k points) | 8 views

+1 vote

2 answers

23

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 Veteran (52.9k points) | 21 views

0 votes

0 answers

24

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 Veteran (52.9k points) | 6 views

0 votes

0 answers

25

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 Veteran (52.9k points) | 3 views

0 votes

0 answers

26

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 Veteran (52.9k points) | 9 views

0 votes

0 answers

27

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 (15.1k points) | 27 views

0 votes

0 answers

28

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 (15.1k points) | 13 views

0 votes

0 answers

29

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 (15.1k points) | 6 views

0 votes

0 answers

30

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 (15.1k points) | 10 views

Page:

1
2
3
4
5
6
7
next »

Recent questions tagged context-free-grammars

50,666 questions

56,165 answers

193,790 comments

93,874 users