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 contextfreegrammars
0
votes
0
answers
1
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 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
2
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 15
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

33
views
peterlinz
theoryofcomputation
contextfreegrammars
+1
vote
0
answers
3
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

57
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
4
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

15
views
peterlinz
theoryofcomputation
contextfreegrammars
ambiguous
0
votes
0
answers
5
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

20
views
peterlinz
theoryofcomputation
contextfreegrammars
ambiguous
0
votes
0
answers
6
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

28
views
peterlinz
theoryofcomputation
contextfreegrammars
parsing
0
votes
0
answers
7
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
8
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

4
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
9
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

4
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
10
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

4
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
11
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

7
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
12
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

5
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
13
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

7
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
14
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

3
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
15
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

7
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
16
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

13
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
17
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

6
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
18
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

11
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
19
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

14
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
20
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

25
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
21
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

14
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
22
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

18
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
23
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

16
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
24
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 14
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
25
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 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

14
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
26
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 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
contextfreelanguage
0
votes
0
answers
27
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 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

24
views
peterlinz
theoryofcomputation
contextfreelanguage
contextfreegrammars
0
votes
0
answers
28
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 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

8
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
29
Peter Linz Edition 4 Exercise 5.1 Question 4 (Page No. 133)
Show that the grammar with productions $S\rightarrow aSbSS\lambda$ does in fact generate the language $L=$ {$w∈ $ {$a,b$}$^*:n_a(w)=n_b(w) $ and $n_a(v)\geq n_b(v),$ where $v$ is any prefix of $w$}.
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

20
views
peterlinz
theoryofcomputation
contextfreegrammars
+1
vote
0
answers
30
Peter Linz Edition 4 Exercise 5.1 Question 3 (Page No. 133)
Give a derivation tree for $w = abbbaabbaba$ for the grammar $G$, with productions $S\rightarrow abB$ $A\rightarrow aaBb$ $B\rightarrow bbAa$ $A\rightarrow \lambda$. Use the derivation tree to find a leftmost derivation.
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

21
views
peterlinz
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
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 contextfreegrammars
Recent Blog Comments
Even In 2019 my 16 questions goes for negative...
It's a question not a post..
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
50,647
questions
56,492
answers
195,461
comments
100,762
users