Recent questions tagged context-free-grammars

Recent questions tagged context-free-grammars

0 votes

1 answer

1

made easy test series - parsing - context-free grammar
Consider the following context-free grammar: Find the number of unique productions in {Goto (A → D.BC, B) U Goto (A → .DBC, D)}

atulcse asked in Compiler Design Jan 16

173 views

3 votes

2 answers

2

#Gate CS Applied Course Mock Test
Is this Language a CFL? If yes, Can you please explain the implementation.

Rajesh Reddy asked in Theory of Computation Jan 3

by Rajesh Reddy

261 views

0 votes

1 answer

3

Compiler Design
In this question I got 5 as answer but according to made easy it’s 6

Sagar475 asked in Compiler Design Jan 1

124 views

1 vote

1 answer

4

Test series Made easy
How to solve this ? Please help.

raja11sep asked in Compiler Design Dec 31, 2021

305 views

2 votes

1 answer

5

Greibach Normal Form
Convert the following grammar into Greibach Normal Form. E-> E + T | T T-> T*F | F F->(E) | a I am unable to process this type of grammer into GNF, Can someone please provide a detailed explaination?

hustlerrr asked in Theory of Computation Nov 17, 2021

383 views

3 votes

1 answer

6

Applied Test Series
How to approach with such questions. Do we have to generate strings to validate the property of the grammars ?

LRU asked in Theory of Computation Oct 3, 2021

by LRU

149 views

1 vote

2 answers

7

can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not. Can someone share the approach for second part.

mk_007 asked in Theory of Computation Oct 3, 2021

by mk_007

120 views

0 votes

1 answer

8

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 10
Consider an $\varepsilon$-tree CFG. If for every pair of productions $A\rightarrow u$ and $A\rightarrow v$ If $\text{FIRST(u)} \cap \text{FIRST(v)}$ is empty then the CFG has to be $LL(1).$ If the CFG is $LL(1)$ then $\text{FIRST(u)} \cap \text{FIRST(v)}$ has to be empty. Both $(A)$ and $(B)$ None of the above

Lakshman Patel RJIT asked in Compiler Design Apr 1, 2020

by Lakshman Patel RJIT

2.6k views

0 votes

1 answer

9

NIELIT 2016 MAR Scientist B - Section C: 29
The CFG $S \to aS\mid bS\mid a\mid b$ is equivalent to $(a+b)$ $(a+b)(a+b)^*$ $(a+b)(a+b)$ all of these

Lakshman Patel RJIT asked in Theory of Computation Mar 31, 2020

by Lakshman Patel RJIT

840 views

0 votes

1 answer

10

NIELIT 2017 DEC Scientist B - Section B: 7
Let $G$ be a grammar in CFG and let $W_1,W_2\in L(G)$ such that $\mid W_1\mid=\mid W_2\mid$ then which of the following statements is true? Any derivation of $W_1$ has exactly the same number of steps as any derivation ... $W_1$ may be shorter than the derivation of $W_2$ None of the options

Lakshman Patel RJIT asked in Theory of Computation Mar 30, 2020

by Lakshman Patel RJIT

567 views

0 votes

1 answer

11

NIELIT 2017 DEC Scientist B - Section B: 26
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG

Lakshman Patel RJIT asked in Compiler Design Mar 30, 2020

by Lakshman Patel RJIT

814 views

0 votes

2 answers

12

UGC NET CSE | January 2017 | Part 3 | Question: 22
Let $G= (V,T,S,P)$ be a context-free grammer such that every one of its productions is of the form $A\rightarrow v$, with $\mid v \mid=K> 1$. The derivation tree for any $W \in L(G)$ has a height $h$ ... $\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid - 1}{K-1} \right)$

go_editor asked in Theory of Computation Mar 24, 2020

311 views

1 vote

4 answers

13

ISRO2020-39
The language which is generated by the grammar $S \rightarrow aSa \mid bSb \mid a \mid b$ over the alphabet of $\{a,b\}$ is the set of Strings that begin and end with the same symbol All odd and even length palindromes All odd length palindromes All even length palindromes

Satbir asked in Theory of Computation Jan 13, 2020

by Satbir

977 views

3 votes

0 answers

14

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 20, 2019

by Lakshman Patel RJIT

434 views

0 votes

0 answers

15

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}\}$.

Lakshman Patel RJIT asked in Theory of Computation Oct 20, 2019

by Lakshman Patel RJIT

334 views

0 votes

0 answers

16

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.)

Lakshman Patel RJIT asked in Theory of Computation Oct 19, 2019

by Lakshman Patel RJIT

178 views

0 votes

0 answers

17

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

Lakshman Patel RJIT asked in Theory of Computation Oct 17, 2019

by Lakshman Patel RJIT

112 views

0 votes

0 answers

18

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

Lakshman Patel RJIT asked in Theory of Computation Oct 17, 2019

by Lakshman Patel RJIT

107 views

0 votes

0 answers

19

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 17, 2019

by Lakshman Patel RJIT

293 views

0 votes

0 answers

20

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 17, 2019

by Lakshman Patel RJIT

158 views

0 votes

0 answers

21

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}$.)

Lakshman Patel RJIT asked in Theory of Computation Oct 17, 2019

by Lakshman Patel RJIT

99 views

0 votes

0 answers

22

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

202 views

1 vote

0 answers

23

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$

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

128 views

0 votes

0 answers

24

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).

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

141 views

0 votes

0 answers

25

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

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

147 views

Page:

1
2
3
4
5
6
...
9
next »

Follow @gateoverflow

Recent questions tagged context-free-grammars

Search GATE Overflow for GATE CSE