The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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 contextfreegrammars
0
votes
0
answers
1
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 contextfree language.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3

24
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3

23
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
3
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, 2019
in
Theory of Computation
by
Naveen Kumar 3

32
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
4
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, 2019
in
Theory of Computation
by
Naveen Kumar 3

23
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
1
answer
5
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, 2019
in
Theory of Computation
by
Naveen Kumar 3

43
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
6
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 SSaSbab$.
asked
Jun 25, 2019
in
Theory of Computation
by
Naveen Kumar 3

23
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
+1
vote
1
answer
7
ISI2018PCBCS4
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, 2019
in
Theory of Computation
by
akash.dinkar12

118
views
isi2018pcbcs
theoryofcomputation
contextfreegrammars
descriptive
0
votes
1
answer
8
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

54
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
9
Michael Sipser Edition 3 Exercise 2 Question 27 (Page No. 157)
$G$ is a naturallooking 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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

68
views
michaelsipser
theoryofcomputation
contextfreegrammars
ambiguousgrammar
+1
vote
1
answer
10
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

38
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
proof
0
votes
1
answer
11
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 contextfree language$.$
asked
May 4, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

35
views
michaelsipser
theoryofcomputation
contextfreegrammars
0
votes
1
answer
12
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

28
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
13
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

32
views
michaelsipser
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
14
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 contextfree 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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

36
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
1
answer
15
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

59
views
michaelsipser
theoryofcomputation
contextfreegrammars
cnf
0
votes
1
answer
16
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

51
views
michaelsipser
theoryofcomputation
contextfreegrammars
regularlanguages
0
votes
0
answers
17
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, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

51
views
michaelsipser
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
18
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 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

20
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
1
answer
19
Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)
Give contextfree 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 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

44
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
1
answer
20
Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give contextfree 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{{$ww=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
asked
May 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

50
views
michaelsipser
theoryofcomputation
contextfreelanguages
contextfreegrammars
descriptive
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 2 Question 3 (Page No. 155)
Answer each part for the following contextfree 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 2, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

37
views
michaelsipser
theoryofcomputation
contextfreegrammars
descriptive
0
votes
0
answers
22
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+TT$ $T\rightarrow T\times FF$ $F\rightarrow (E)a$ Give parse trees and derivations for each string. $a$ $a+a$ $a+a+a$ $((a))$
asked
May 1, 2019
in
Theory of Computation
by
Lakshman Patel RJIT

42
views
michaelsipser
theoryofcomputation
contextfreegrammars
parsetrees
0
votes
0
answers
23
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 → aSbb$.
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

29
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
24
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, 2019
in
Theory of Computation
by
Naveen Kumar 3

31
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
25
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 BBa,$ $B\rightarrow ABb.$
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

41
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
26
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 BBa,$ $B\rightarrow ABb.$
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

37
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 6.2 Question 16 (Page No. 170)
“Twostandard form is general; for any contextfree grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in twostandard form.” Prove this.
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

32
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 6.2 Question 15 (Page No. 170)
A contextfree grammar is said to be in twostandard 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 twostandard form.
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

16
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
29
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, 2019
in
Theory of Computation
by
Naveen Kumar 3

45
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
gnf
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 6.2 Question 13 (Page No. 170)
Convert the grammar $S\rightarrow ABba,$ $A\rightarrow aaAB,$ $B\rightarrow bAb$ into Greibach normal form.
asked
Apr 19, 2019
in
Theory of Computation
by
Naveen Kumar 3

19
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
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
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged contextfreegrammars
Recent Blog Comments
Thank brother !! Bookmarked it :)
Check out goxul.github.io, it has all the...
congratulation brother ! Can you please tell me...
I got selected for this, in case someone lands up...
After the written exam and at the time of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,582
answers
202,000
comments
95,401
users