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 5.1 Question 2 (Page No. 133)
Draw the derivation tree corresponding to the derivation in Example 5.1. Example 5.1 The grammar $G = (${$S$}, {$a, b$}$, S, P),$ with productions $S\rightarrow aSa$ $S\rightarrow bSb$ $S\rightarrow \lambda$ is contextfree. A typical derivation in this grammar is $S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabbaa.$
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

23
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
2
Peter Linz Edition 4 Exercise 5.1 Question 1 (Page No. 133)
Find the language generated by following grammar: The grammar G, with productions $S\rightarrow abB$ $A\rightarrow aaBb$ $B\rightarrow bbAa$ $A\rightarrow \lambda$
asked
Apr 13
in
Theory of Computation
by
Naveen Kumar 3
Boss
(
15.2k
points)

21
views
peterlinz
theoryofcomputation
contextfreegrammars
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 7.4 Question 5 (Page No. 308)
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

24
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 7.4 Question 4 (Page No. 308)
Show that in any $CNF$ grammar all parse trees for strings of length $n$ have $2n1$ interior nodes $(i.e.,$ $2n1$ nodes with variables for lables$).$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

22
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
5
Ullman (TOC) Edition 3 Exercise 7.4 Question 3 (Page No. 308)
Using the grammar $G$ of Example $7.34,$use the $CYK$ algorithm to determine whether each of the following strings is in $L(G):$ $ababa$ $baaab$ $aabab$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

27
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 7.4 Question 2 (Page No. 308)
Use the technique described in Section $7.4.3$ to develop linear time algorithms for the following questions about $CFG's:$ Which symbols appear in some sentential form$?$ Which symbols are nullable $\text{(derive $\in$)?}$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

8
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
7
Ullman (TOC) Edition 3 Exercise 7.1 Question 12 (Page No. 279)
Use the construction of question $11$ to convert the grammar $S\rightarrow AA0$ $A\rightarrow SS1$ to $GNF.$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 7.1 Question 11 (Page No. 278  279)
In this exercise, we shall show that for every contextfree language $L$ containing at least one string other than $\in,$there is a $CFG$ in Greibach normal form that generates $L\in.$ Recall that a Greibach normal form $(GNF)$ grammar is ... $(a).$ Then fi x the $B_{i}$ productions in any order , again $(a).$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
proof
descriptive
0
votes
0
answers
9
Ullman (TOC) Edition 3 Exercise 7.1 Question 10 (Page No. 278)
Is it possible to find, for every contextfree language without $\in,$ a grammar such that all its productions are either of the form $A\rightarrow BCD$ $($i.e., a body consisting of three variables$),$ or $A\rightarrow a$ $($i.e., a body consisting of a single terminal$)?$ Give either a proof or a counterexample.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
proof
0
votes
0
answers
10
Ullman (TOC) Edition 3 Exercise 7.1 Question 9 (Page No. 278)
Provide the inductive proofs needed to complete the following theorems$:$ The part of Theorem $7.4$ where we show that discovered symbols really are generating. Both directions of Theorem $7.6$ where we show the correctness of ... reachable symbols. The part of Theorem $7.11$ where we show that all pairs discovered really are unit pairs.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
proof
0
votes
0
answers
11
Ullman (TOC) Edition 3 Exercise 7.1 Question 8 (Page No. 278)
Let $G$ be an $\in$productionfree grammar whose total length of production bodies is $n.$ We convert $G$ to $CNF.$ Show that the CNF grammar has at most $O(n^{2})$ productions. Show that it is ... $n^{2}.$ Hint$:$Consider the construction that eliminates unit productions.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

14
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
12
Ullman (TOC) Edition 3 Exercise 7.1 Question 7 (Page No. 278)
Suppose $G$ is a CFG with $p$ productions, and no production body longer than $n.$Show that if $A\xrightarrow[G]{*}\in,$ then there is a derivation of $\in$ from $A$ of no more than $\frac{(n^{p}1)}{(n1)}$ steps. How close can you actually come to this bound$?$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

17
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
13
Ullman (TOC) Edition 3 Exercise 7.1 Question 6 (Page No. 278)
Design a CNF grammar for the set of strings of balanced parentheses.You need not start from any particular nonCNF grammar.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

12
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
14
Ullman (TOC) Edition 3 Exercise 7.1 Question 5 (Page No. 277  278)
Begin with the grammar$:$ $S\rightarrow aAabBb\in$ $A\rightarrow Ca$ $B\rightarrow Cb$ $C\rightarrow CDE\in$ $D\rightarrow ABab$ Eliminate $\in$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

10
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
15
Ullman (TOC) Edition 3 Exercise 7.1 Question 4 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow AAAB$ $A\rightarrow aAB$ $B\rightarrow \in$ Eliminate $\in$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

27
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
16
Ullman (TOC) Edition 3 Exercise 7.1 Question 3 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow 0A01B1BB$ $A\rightarrow C$ $B\rightarrow SA$ $C\rightarrow S\in$ Eliminate $\in$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
ullman
theoryofcomputation
contextfreelanguages
contextfreegrammars
0
votes
0
answers
17
Ullman (TOC) Edition 3 Exercise 7.1 Question 2 (Page No. 275  276  277)
Begin with grammar$:$ $S\rightarrow ASB\in$ $A\rightarrow aASa$ $B\rightarrow SbSAbb$ Eliminate $\in$productions. Eliminate any unit productions in the resulting grammar. Eliminate any useless symbols in the resulting grammar. Put the resulting grammar into Chomsky Normal Form.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
ullman
theoryofcomputation
contextfreegrammars
0
votes
1
answer
18
Ullman (TOC) Edition 3 Exercise 7.1 Question 1 (Page No. 275)
Find a grammar equivalent to $S\rightarrow ABCA$ $A\rightarrow a$ $B\rightarrow BCAB$ $C\rightarrow aBb$ with no useless symbols.
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

27
views
ullman
theoryofcomputation
contextfreegrammars
0
votes
0
answers
19
Ullman (TOC) Edition 3 Exercise 6.4 Question 1 (Page No. 256)
For each of the following PDA's, tell whether or not it is deterministic. Either show that it meets the definition of a DPDA or find a rule or rules that violate it. $a)$ $b)$ Suppose the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ ... $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

16
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
20
Ullman (TOC) Edition 3 Exercise 6.3 Question 7 (Page No. 252)
Suppose we have a PDA with $s$ states $t$ stack symbols and no rule in which a replacement stack string has a length greater than $u.$ Give a tight upper bound on the number of variables in the $CFG$ that we construct for this PDA by the method of an empty stack.
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

30
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
21
Ullman (TOC) Edition 3 Exercise 6.3 Question 5 (Page No. 252)
Below are some contextfree languages.For each,devise a PDA that accepts the language by empty stack. You may ,if you wish, first construct a grammar for the language, and then convert to a $PDA:$ $\{a^{n}b^{m}c^{2(n+m)}n\geq 0,m\geq 0\}$ $\{a^{i}b^{j}c^{k}i=2j $(or)$ j=2k\}$ $\{0^{n}1^{m}n\leq m\leq 2n\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

21
views
ullman
theoryofcomputation
contextfreegrammars
pushdownautomata
0
votes
0
answers
22
Ullman (TOC) Edition 3 Exercise 6.3 Question 4 (Page No. 252)
Convert the $PDA, $ $P=(\{q,p\},\{0,1\},\{Z_{0},X\},\delta,q,Z_{0}.\{p\})$ to a $CFG,$ if $\delta$ given by $:$ $\delta(q,0,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,0,X)=\{(q,XX)\}$ $\delta(q,1,X)=\{(q,X)\}$ $\delta(q,\in,X)=\{p,\in\}$ $\delta(p,\in,X)=\{p,\in\}$ $\delta(p,1,X)=\{(p,XX)\}$ $\delta(p,1,Z_{0})=\{p,\in\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

8
views
ullman
theoryofcomputation
pushdownautomata
contextfreegrammars
0
votes
0
answers
23
Ullman (TOC) Edition 3 Exercise 6.3 Question 3 (Page No. 251)
Convert the $PDA$ $P=(\{p,q\},\{0,1\},\{X,Z_{0}\},\delta.q.Z_{0})$ to a $CFG,$ if $\delta$ is given by $:$ $\delta(q,1,Z_{0})=\{(q,XZ_{0})\}$ $\delta(q,1,X)=\{(q,XX)\}$ $\delta(q,0,X)=\{(p,X)\}$ $\delta(q,\in,X)=\{(q,\in)\}$ $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
asked
Apr 7
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

8
views
ullman
pushdownautomata
contextfreegrammars
0
votes
0
answers
24
Ullman (TOC) Edition 3 Exercise 5.4 Question 7 (Page No. 216)
The following grammar generates prefix expressions with operands $x$ and $y$ and binary operators $+,$ and $*$ $:$ $E\rightarrow +EE*EEEExy$ Find leftmost and rightmost derivations and a derivation tree for the string $+*xyxy.$ Prove that this grammar is unambiguous.
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

20
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
25
Ullman (TOC) Edition 3 Exercise 5.4 Question 6 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A\in$ $B\rightarrow 0B1B\in$ Is your grammar is unambiguous$?$ If not,redesign it to be unambiguous.
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

7
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
26
Ullman (TOC) Edition 3 Exercise 5.4 Question 5 (Page No. 216)
This question concerns the grammar $S\rightarrow A1B$ $A\rightarrow 0A\in$ $B\rightarrow 0B1B\in$ Show that this grammar is unambiguous. Find a grammar for the same language that is ambiguous and demonstrate its ambiguity.
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

9
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
27
Ullman (TOC) Edition 3 Exercise 5.4 Question 4 (Page No. 216)
Some strings of $a's$ and $b's$ have a unique parse tree in the grammar of $S\rightarrow aSaSbS\in.$ Give an efficient test to tell whether a given string is one of these. The test $"$try all parse trees to see how many yield the given string$"$ is not adequately efficient$.$
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

14
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
28
Ullman (TOC) Edition 3 Exercise 5.4 Question 3 (Page No. 216)
Find an unambiguous grammar for the language of $S\rightarrow aSaSbS\in$
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

8
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
29
Ullman (TOC) Edition 3 Exercise 5.4 Question 2 (Page No. 216)
Prove that the grammar generates all only the strings of $a's$ and $b's$ such that every prefix has at least as many $a's$ as $b's.$ $S\rightarrow aSaSbS\in$
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

4
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
0
votes
0
answers
30
Ullman (TOC) Edition 3 Exercise 5.4 Question 1 (Page No. 215)
Consider the grammar $S\rightarrow aSaSbS\in$ This grammar is ambiguous. Show in particular that the string $aab$ has two$:$ Parse trees Leftmost derivations Rightmost derivations
asked
Apr 6
in
Theory of Computation
by
Lakshman Patel RJIT
Veteran
(
55k
points)

6
views
ullman
theoryofcomputation
contextfreegrammars
contextfreelanguages
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged contextfreegrammars
Recent Blog Comments
Not really. It was excluding shipping I guess....
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
50,645
questions
56,616
answers
195,897
comments
102,353
users