Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions tagged context-free-grammar
0
votes
0
answers
181
Peter Linz Edition 4 Exercise 5.1 Question 10 (Page No. 134)
Find a context-free 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.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 14, 2019
by
Naveen Kumar 3
235
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
0
votes
1
answer
182
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 context-free language.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
304
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
0
votes
4
answers
183
Peter Linz Edition 4 Exercise 5.1 Question 8 (Page No. 134)
Find context-free 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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
411
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
0
votes
6
answers
184
Peter Linz Edition 4 Exercise 5.1 Question 7 (Page No. 133)
Find context-free 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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
921
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
185
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$.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
260
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
0
votes
0
answers
186
Peter Linz Edition 4 Exercise 5.1 Question 4 (Page No. 133)
Show that the grammar with productions $S\rightarrow aSb|SS|\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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
193
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
2
votes
0
answers
187
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.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
172
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
0
votes
0
answers
188
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 context-free. A typical derivation in this grammar is $S\Rightarrow aSa\Rightarrow aaSaa\Rightarrow aabSbaa\Rightarrow aabbaa.$
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
212
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
0
votes
1
answer
189
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$
Naveen Kumar 3
asked
in
Theory of Computation
Apr 13, 2019
by
Naveen Kumar 3
192
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
0
votes
0
answers
190
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$.$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
313
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
191
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 $2n-1$ interior nodes $(i.e.,$ $2n-1$ nodes with variables for lables$).$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
158
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
192
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$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
261
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
193
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$)?}$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
128
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
194
Ullman (TOC) Edition 3 Exercise 7.1 Question 12 (Page No. 279)
Use the construction of question $11$ to convert the grammar $S\rightarrow AA|0$ $A\rightarrow SS|1$ to $GNF.$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
126
views
ullman
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
195
Ullman (TOC) Edition 3 Exercise 7.1 Question 11 (Page No. 278 - 279)
In this exercise, we shall show that for every context-free 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).$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
290
views
ullman
theory-of-computation
context-free-language
context-free-grammar
proof
descriptive
0
votes
0
answers
196
Ullman (TOC) Edition 3 Exercise 7.1 Question 10 (Page No. 278)
Is it possible to find, for every context-free 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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
231
views
ullman
theory-of-computation
context-free-language
context-free-grammar
proof
0
votes
0
answers
197
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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
316
views
ullman
theory-of-computation
context-free-language
context-free-grammar
proof
0
votes
0
answers
198
Ullman (TOC) Edition 3 Exercise 7.1 Question 8 (Page No. 278)
Let $G$ be an $\in-$production-free 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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
360
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
199
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)}{(n-1)}$ steps. How close can you actually come to this bound$?$
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
267
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
200
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 non-CNF grammar.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
261
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
201
Ullman (TOC) Edition 3 Exercise 7.1 Question 5 (Page No. 277 - 278)
Begin with the grammar$:$ $S\rightarrow aAa|bBb|\in$ $A\rightarrow C|a$ $B\rightarrow C|b$ $C\rightarrow CDE|\in$ $D\rightarrow A|B|ab$ 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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
236
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
202
Ullman (TOC) Edition 3 Exercise 7.1 Question 4 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow AAA|B$ $A\rightarrow aA|B$ $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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
200
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
203
Ullman (TOC) Edition 3 Exercise 7.1 Question 3 (Page No. 277)
Begin with the grammar$:$ $S\rightarrow 0A0|1B1|BB$ $A\rightarrow C$ $B\rightarrow S|A$ $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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
216
views
ullman
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
204
Ullman (TOC) Edition 3 Exercise 7.1 Question 2 (Page No. 275 - 276 - 277)
Begin with grammar$:$ $S\rightarrow ASB|\in$ $A\rightarrow aAS|a$ $B\rightarrow SbS|A|bb$ 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.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
250
views
ullman
theory-of-computation
context-free-grammar
0
votes
1
answer
205
Ullman (TOC) Edition 3 Exercise 7.1 Question 1 (Page No. 275)
Find a grammar equivalent to $S\rightarrow AB|CA$ $A\rightarrow a$ $B\rightarrow BC|AB$ $C\rightarrow aB|b$ with no useless symbols.
admin
asked
in
Theory of Computation
Apr 11, 2019
by
admin
1.2k
views
ullman
theory-of-computation
context-free-grammar
0
votes
0
answers
206
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, $ ... $\delta(p,1,X)=\{(p,\in)\}$ $\delta(p,0,Z_{0})=\{(q,Z_{0})\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
751
views
ullman
theory-of-computation
pushdown-automata
context-free-grammar
0
votes
0
answers
207
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.
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
371
views
ullman
theory-of-computation
pushdown-automata
context-free-grammar
0
votes
0
answers
208
Ullman (TOC) Edition 3 Exercise 6.3 Question 5 (Page No. 252)
Below are some context-free 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\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
278
views
ullman
theory-of-computation
context-free-grammar
pushdown-automata
0
votes
0
answers
209
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\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
181
views
ullman
theory-of-computation
pushdown-automata
context-free-grammar
0
votes
0
answers
210
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})\}$
admin
asked
in
Theory of Computation
Apr 7, 2019
by
admin
147
views
ullman
pushdown-automata
context-free-grammar
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
12
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged context-free-grammar
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...