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 6.1 Question 4 (Page No. 161)
In Theorem 6.1, why is it necessary to assume that $A$ and $B$ are different variables?
asked
Apr 16, 2019
in
Theory of Computation
by
Naveen Kumar 3

47
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 6.1 Question 3 (Page No. 161)
Show that the two grammars $S\rightarrow abABba,$ $A\rightarrow aaa,$ $B\rightarrow aAbb$ and $S\rightarrow abAaAabAbbba,$ $A\rightarrow aaa$ are equivalent.
asked
Apr 16, 2019
in
Theory of Computation
by
Naveen Kumar 3

32
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
3
Peter Linz Edition 4 Exercise 6.1 Question 2 (Page No. 161)
Show a derivation tree for the string $ababbac$, using grammar with productions $A\rightarrow aaaAabBC,$ $B\rightarrow abbAb.$ also show the derivation tree for grammar with productions $A\rightarrow aaaAababbAcabbc,$ $B\rightarrow abbAb.$
asked
Apr 16, 2019
in
Theory of Computation
by
Naveen Kumar 3

15
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
4
Peter Linz Edition 4 Exercise 6.1 Question 1 (Page No. 161)
Complete the proof of Theorem 6.1 by showing that $S\overset{*}{\Rightarrow}_{\widehat{G}} w$ implies $S\overset{*}{\Rightarrow}_{G} w$. Theorem 6.1 Let $G = (V, T, S, P)$ be a contextfree grammar. Suppose that $P$ ... $P$, and adding to it $A\rightarrow x_1y_1x_2x_1y_2x_2...x_1y_nx_2.$ Then, $L(\widehat{G})=L(G)$.
asked
Apr 16, 2019
in
Theory of Computation
by
Naveen Kumar 3

69
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
+1
vote
0
answers
5
Peter Linz Edition 4 Exercise 5.2 Question 20 (Page No. 145)
Find a grammar equivalent to $S\rightarrow aAB, A\rightarrow bBb, B\rightarrow A\lambda$ that satisfies the conditions of Theorem 5.2. Theorem 5.2 Suppose that $G = (V, T, S, P)$ is a contextfree grammar that does not have ... algorithm which, for any $w ∈ Σ^*,$ either produces a parsing of $w$ or tells us that no parsing is possible.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

106
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
6
Peter Linz Edition 4 Exercise 5.2 Question 19 (Page No. 145)
Prove the following result. Let $G = (V, T, S, P )$ be a contextfree grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unambiguous.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

24
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
ambiguous
0
votes
0
answers
7
Peter Linz Edition 4 Exercise 5.2 Question 18 (Page No. 145)
Is the string $aabbababb$ in the language generated by the grammar $S → aSSb$? Show that the grammar with productions $S\rightarrow aAb\lambda,$ $A\rightarrow aAb\lambda$ is unambiguous.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

29
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
ambiguous
0
votes
0
answers
8
Peter Linz Edition 4 Exercise 5.2 Question 17 (Page No. 145)
Use the exhaustive search parsing method to parse the string $abbbbbb$ with the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A\lambda.$ In general, how many rounds will be needed to parse any string $w$ in this language?
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

54
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
parsing
0
votes
0
answers
9
Peter Linz Edition 4 Exercise 5.1 Question 27 (Page No. 135)
Let $G = (V,T,S,P)$ be a contextfree grammar such that every one of its productions is of the form $A → v,$ with $v = k > 1.$ Show that the derivation tree for any $w ∈ L(G)$ has a height $h$ such that $\log_{k}w\leq h\leq \frac{(w1)}{k1}$.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

46
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
10
Peter Linz Edition 4 Exercise 5.1 Question 26 (Page No. 135)
Find a linear grammar for the language $L=$ {$a^nb^m:n\neq m$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

13
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
11
Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a contextfree grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

12
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
12
Peter Linz Edition 4 Exercise 5.1 Question 24 (Page No. 135)
Find a contextfree grammar that can generate all the production rules for contextfree grammars with $T =$ {$a, b$} and $V =$ {$A, B, C$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

8
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
13
Peter Linz Edition 4 Exercise 5.1 Question 23 (Page No. 135)
Find a contextfree grammar for the set of all regular expressions on the alphabet {$a, b$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

12
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
14
Peter Linz Edition 4 Exercise 5.1 Question 22 (Page No. 135)
Define what one might mean by properly nested parenthesis structures involving two kinds of parentheses, say ( ) and [ ]. Intuitively, properly nested strings in this situation are ([ ]), ([[ ]])[( )], but not ([ )] or (( ]]. Using your definition, give a contextfree grammar for generating all properly nested parentheses.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

8
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
15
Peter Linz Edition 4 Exercise 5.1 Question 21 (Page No. 135)
Consider the derivation tree below. Find a grammar $G$ for which this is the derivation tree of the string $aab$. Then find two more sentences of $L(G)$. Find a sentence in $L(G)$ that has a derivation tree of height five or larger.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

21
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
16
Peter Linz Edition 4 Exercise 5.1 Question 20 (Page No. 135)
Consider the grammar with productions $S\rightarrow aaB,$ $A\rightarrow bBb\lambda,$ $B\rightarrow Aa.$ Show that the string $aabbabba$ is not in the language generated by this grammar.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

9
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
17
Peter Linz Edition 4 Exercise 5.1 Question 19 (Page No. 134)
Show a derivation tree for the string $aabbbb$ with the grammar $S\rightarrow AB\lambda,$ $A\rightarrow aB,$ $B\rightarrow Sb.$ Give a verbal description of the language generated by this grammar.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

18
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
18
Peter Linz Edition 4 Exercise 5.1 Question 18 (Page No. 134)
Show that the language $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^+,w_1\neq w_2^R$}, with $Σ =$ {$a,b,c$},is contextfree.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

24
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
19
Peter Linz Edition 4 Exercise 5.1 Question 17 (Page No. 134)
Show that the complement of the language $L =$ {$a^nb^mc^k : k = n + m$} is contextfree.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

17
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
20
Peter Linz Edition 4 Exercise 5.1 Question 16 (Page No. 134)
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is contextfree.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

17
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
21
Peter Linz Edition 4 Exercise 5.1 Question 15 (Page No. 134)
Show that the following language is contextfree. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,u=w=2$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

31
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
22
Peter Linz Edition 4 Exercise 5.1 Question 14 (Page No. 134)
Let $L_1$ be the language $L_1 =$ {$a^nb^mc^k : n = m$ or $m ≤ k$} and $L_2$ the language $L_2 =$ {$a^nb^mc^k : n + 2m = k$}. Show that $L_1 ∪ L_2$ is a contextfree language.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

35
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
23
Peter Linz Edition 4 Exercise 5.1 Question 13 (Page No. 134)
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peterlinzedition4exercise51question13apageno134 (b) Show that $L^k$ is contextfree for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are contextfree.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

27
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
24
Peter Linz Edition 4 Exercise 5.1 Question 12 (Page No. 134)
Given a contextfree grammar $G$ for a language $L$, show how one can create from $G$ a grammar $\widehat{G}$ so that $L(\widehat{G}$) = head (L).
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

28
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
25
Peter Linz Edition 4 Exercise 5.1 Question 11 (Page No. 134)
Find a contextfree grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

21
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
26
Peter Linz Edition 4 Exercise 5.1 Question 10 (Page No. 134)
Find a contextfree grammar for $head (L)$, where $L$ is the language $L =$ {$a^nb^m : n ≤ m + 3$}. For the definition of $head$ see Exercise 18, Section 4.1.
asked
Apr 15, 2019
in
Theory of Computation
by
Naveen Kumar 3

31
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
0
votes
0
answers
27
Peter Linz Edition 4 Exercise 5.1 Question 9 (Page No. 134)
Show that $L =$ {$w ∈$ {$a,b,c$}$^* : w = 3n_a(w)$} is a contextfree language.
asked
Apr 14, 2019
in
Theory of Computation
by
Naveen Kumar 3

26
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
28
Peter Linz Edition 4 Exercise 5.1 Question 8 (Page No. 134)
Find contextfree grammars for the following languages (with $n ≥ 0, m ≥ 0, k ≥ 0$). (a) $L =$ {$a^nb^mc^k : n = m$ or $m ≤ k$}. (b) $L =$ {$a^nb^mc^k : n = m$ or $m ≠ k$}. (c) $L =$ {$a^nb^mc^k : k = n + m$}. (d) $L =$ ... $L =$ {$a^nb^mc^k, k ≠ n + m$}. (h) $L =$ {$a^nb^mc^k : k ≥ 3$}.
asked
Apr 14, 2019
in
Theory of Computation
by
Naveen Kumar 3

49
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 5.1 Question 7 (Page No. 133)
Find contextfree grammars for the following languages (with $n ≥ 0, m ≥ 0$). (a) $L =$ {$a^nb^m : n ≤ m + 3$}. (b) $L =$ {$a^nb^m : n ≠ m − 1$ ... $v$ is any prefix of $w$}. (g) $L =$ {$w ∈$ {$a,b$}$^* : n_a (w) = 2n_b(w) + 1$}.
asked
Apr 14, 2019
in
Theory of Computation
by
Naveen Kumar 3

65
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
30
Peter Linz Edition 4 Exercise 5.1 Question 6 (Page No. 133)
Give the Complete proof of Theorem 5.1 by showing that the yield of every partial derivation tree with root $S$ is a sentential form of $G$. Theorem 5.1 Let $G = (V, T, S, P )$ ... any partial derivation tree for $G$ whose root is labeled $S$, then the yield of $t_G$ is a sentential form of $G$.
asked
Apr 14, 2019
in
Theory of Computation
by
Naveen Kumar 3

24
views
peterlinz
peterlinzedition4
theoryofcomputation
contextfreegrammars
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
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
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
Can someone tell me how to check part B marks?...
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,487
answers
201,827
comments
95,294
users