The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register
|
I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged context-free-grammars
0
votes
1
answer
1
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
(
15.2k
points)
|
11
views
peter-linz
theory-of-computation
context-free-grammars
context-free-languages
0
votes
0
answers
2
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
(
15.2k
points)
|
9
views
peter-linz
theory-of-computation
context-free-grammars
context-free-languages
0
votes
1
answer
3
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
(
15.2k
points)
|
14
views
peter-linz
theory-of-computation
context-free-languages
context-free-grammars
0
votes
0
answers
4
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
(
15.2k
points)
|
10
views
peter-linz
theory-of-computation
context-free-grammars
+1
vote
1
answer
5
ISI2018-PCB-CS4
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 ... 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.9k
points)
|
34
views
isi2018-pcb-cs
theory-of-computation
context-free-grammars
descriptive
0
votes
1
answer
6
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
Veteran
(
54.9k
points)
|
30
views
michael-sipser
theory-of-computation
context-free-grammars
0
votes
1
answer
7
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
Veteran
(
54.9k
points)
|
33
views
michael-sipser
theory-of-computation
context-free-grammars
ambiguous-grammar
+1
vote
1
answer
8
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
Veteran
(
54.9k
points)
|
26
views
michael-sipser
theory-of-computation
context-free-grammars
cnf
proof
0
votes
1
answer
9
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
Veteran
(
54.9k
points)
|
27
views
michael-sipser
theory-of-computation
context-free-grammars
0
votes
1
answer
10
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
Veteran
(
54.9k
points)
|
14
views
michael-sipser
theory-of-computation
context-free-grammars
context-free-languages
0
votes
0
answers
11
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
Veteran
(
54.9k
points)
|
16
views
michael-sipser
theory-of-computation
context-free-grammars
context-free-languages
0
votes
0
answers
12
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
Veteran
(
54.9k
points)
|
19
views
michael-sipser
theory-of-computation
context-free-languages
context-free-grammars
0
votes
1
answer
13
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
Veteran
(
54.9k
points)
|
24
views
michael-sipser
theory-of-computation
context-free-grammars
cnf
0
votes
1
answer
14
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
Veteran
(
54.9k
points)
|
27
views
michael-sipser
theory-of-computation
context-free-grammars
regular-languages
0
votes
0
answers
15
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
Veteran
(
54.9k
points)
|
29
views
michael-sipser
theory-of-computation
context-free-grammars
pushdown-automata
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 2 Question 8 (Page No. 155)
Show that the string the girl touches the boy with the flower has two different leftmost derivations in grammar $G_2$ on $\text{page 103.} $ Describe in English the two different meanings of this sentence.
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)
|
11
views
michael-sipser
theory-of-computation
context-free-languages
context-free-grammars
0
votes
1
answer
17
Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)
Give context-free grammars generating the following languages. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$ The complement of the language $\{a^{n}b^{n}\mid n\geq 0\}$ $\{w\#x\mid w^{R}$ $\text{is a substring of $ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)
|
27
views
michael-sipser
theory-of-computation
context-free-languages
context-free-grammars
0
votes
1
answer
18
Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give context-free grammars that generate the following languages$.$ In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1's}}$ $\text{{w| w starts and ends with the same symbol}}$ ... $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)
|
29
views
michael-sipser
theory-of-computation
context-free-languages
context-free-grammars
descriptive
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 2 Question 3 (Page No. 155)
Answer each part for the following context-free grammar $G.$ $R\rightarrow XRX | S$ $S\rightarrow aT b | bT a$ $T\rightarrow XT X | X | \epsilon$ $X\rightarrow a | b$ What are the variables of $G?$ What are the terminals ... $:S\overset{*}{\Rightarrow}\epsilon.$ Give a description in English of $L(G).$
asked
May 1
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)
|
31
views
michael-sipser
theory-of-computation
context-free-grammars
descriptive
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 2 Question 1 (Page No. 154)
Recall the $\text{CFG}$ $G_{4}$ that we gave in $\text{Example 2.4}.$ For convenience,let’s rename it’s variable with single letters as follows, $E\rightarrow E+T|T$ $T\rightarrow T\times F|F$ $F\rightarrow (E)|a$ Give parse trees and derivations for each string. $a$ $a+a$ $a+a+a$ $((a))$
asked
Apr 30
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
54.9k
points)
|
33
views
michael-sipser
theory-of-computation
context-free-grammars
parse-trees
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 6.3 Question 4 (Page No. 173)
Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
22
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 6.3 Question 3 (Page No. 173)
Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
21
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 6.3 Question 2 (Page No. 173)
Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
27
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 6.3 Question 1 (Page No. 172)
Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in the language generated by the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ $B\rightarrow AB|b.$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
25
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
24
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ $A\rightarrow aB,$ $A\rightarrow a,$ where $A, B, C ∈ V$ and $a ∈ T$. Convert the grammar ... $S\rightarrow aSA,$ $A\rightarrow bABC,$ $B\rightarrow b,$ $C\rightarrow aBC$ into two-standard form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
3
views
peter-linz
theory-of-computation
context-free-grammars
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
27
views
peter-linz
theory-of-computation
context-free-grammars
gnf
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
9
views
peter-linz
theory-of-computation
context-free-grammars
gnf
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 6.2 Question 12 (Page No. 170)
Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
17
views
peter-linz
theory-of-computation
context-free-grammars
gnf
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 6.2 Question 11 (Page No. 170)
Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$
asked
Apr 19
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)
|
20
views
peter-linz
theory-of-computation
context-free-grammars
gnf
Page:
« prev
1
2
3
4
5
6
7
next »
Quick search syntax
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 Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged context-free-grammars
Recent Blog Comments
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
50,644
questions
56,511
answers
195,559
comments
101,073
users