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-language
0
votes
0
answers
151
Michael Sipser Edition 3 Exercise 2 Question 16 (Page No. 156)
Show that the class of context-free languages is closed under the regular operations$,$ union$,$ concatenation, and star$.$
admin
asked
in
Theory of Computation
May 4, 2019
by
admin
207
views
michael-sipser
theory-of-computation
context-free-language
0
votes
0
answers
152
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 context-free 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^{*}.$
admin
asked
in
Theory of Computation
May 4, 2019
by
admin
382
views
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
153
Michael Sipser Edition 3 Exercise 2 Question 11 (Page No. 155)
Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$ $T\rightarrow T\times F\mid F$ $F\rightarrow (E)\mid a$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
301
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
0
answers
154
Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)
Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
966
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
1
answer
155
Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)
Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why or why not$?$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
559
views
michael-sipser
theory-of-computation
context-free-language
ambiguous
grammar
0
votes
0
answers
156
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.
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
294
views
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
1
vote
0
answers
157
Michael Sipser Edition 3 Exercise 2 Question 7 (Page No. 155)
Give informal English descriptions of PDAs for 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}|n\geq 0\}$ $\{w\#x|w^{R}$ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
296
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
1
answer
158
Michael Sipser Edition 3 Exercise 2 Question 6 (Page No. 155)
Give context-free 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}$ ... $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
823
views
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
0
votes
0
answers
159
Michael Sipser Edition 3 Exercise 2 Question 5 (Page No. 155)
Give informal descriptions and state diagrams of pushdown automata for the languages in the following languages In all parts, the alphabet $\sum$ is $\{0,1\}.$ $\text{{w| w contains at least three 1's}}$ ... $\text{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
826
views
michael-sipser
theory-of-computation
context-free-language
pushdown-automata
0
votes
1
answer
160
Michael Sipser Edition 3 Exercise 2 Question 4 (Page No. 155)
Give context-free 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{{$w|w=w^{R},$that is, w is a palindrome}}$ $\text{The empty set}.$
admin
asked
in
Theory of Computation
May 1, 2019
by
admin
3.0k
views
michael-sipser
theory-of-computation
context-free-language
context-free-grammar
descriptive
0
votes
1
answer
161
Michael Sipser Edition 3 Exercise 2 Question 2 (Page No. 154)
Use the languages $A=\{a^{m}b^{n}c^{n}|m,n\geq 0\}$ and $B=\{a^{n}b^{n}c^{m}|m,n\geq 0\}$ together with $\text{Example 2.36}$ to show that the class of context-free languages is not closed under ... $(a)$ and $\text{DeMorgan's law (Theorem 0.20)}$ to show that the class of context-free languages is not closed under complementation.
admin
asked
in
Theory of Computation
Apr 30, 2019
by
admin
462
views
michael-sipser
theory-of-computation
context-free-language
0
votes
0
answers
162
Michael Sipser Edition 3 Exercise 1 Question 73 (Page No. 93)
Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x| x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$
admin
asked
in
Theory of Computation
Apr 30, 2019
by
admin
184
views
michael-sipser
theory-of-computation
context-free-language
proof
descriptive
1
vote
0
answers
163
Peter Linz Edition 4 Exercise 6.1 Question 15 (Page No. 162)
Give an example of a situation in which the removal of $λ$-productions introduces previously nonexistent unit-productions.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 17, 2019
by
Naveen Kumar 3
287
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
1
vote
1
answer
164
Peter Linz Edition 4 Exercise 6.1 Question 8 (Page No. 162)
Remove all unit-productions, all useless productions, and all λ-productions from the grammar $S\rightarrow aA|aBB,$ $A\rightarrow aaA|\lambda,$ $B\rightarrow bB|bbC,$ $C\rightarrow B.$ What language does this grammar generate?
Naveen Kumar 3
asked
in
Theory of Computation
Apr 15, 2019
by
Naveen Kumar 3
2.2k
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
1
vote
1
answer
165
Peter Linz Edition 4 Exercise 6.1 Question 5 (Page No. 161)
Eliminate all useless productions from the grammar $S\rightarrow aS|AB,$ $A\rightarrow bA,$ $B\rightarrow AA.$ What language does this grammar generate?
Naveen Kumar 3
asked
in
Theory of Computation
Apr 15, 2019
by
Naveen Kumar 3
370
views
peter-linz
peter-linz-edition4
context-free-grammar
context-free-language
0
votes
0
answers
166
Peter Linz Edition 5 Exercise 8.1 Question 7(k) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n is prime and m is not prime}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
352
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
1
answer
167
Peter Linz Edition 5 Exercise 8.1 Question 7(j) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m:\text{n is prime or m is prime}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
342
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
168
Peter Linz Edition 5 Exercise 8.1 Question 7(i) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free $L = \{a^nb^m: \text{n and m are both prime}\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
193
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
169
Peter Linz Edition 5 Exercise 8.1 Question 7(h) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w\in\{a,b,c\}^*:n_a(w)+n_b(w)=2n_c(w),n_a(w) = n_b(w)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
290
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
170
Peter Linz Edition 5 Exercise 8.1 Question 7(g) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{w:n_a(w)/n_b(w) = n_c(w)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
173
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
171
Peter Linz Edition 5 Exercise 8.1 Question 7(f) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{w:n_a(w) <n_b(w)<n_c(w)\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
219
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
172
Peter Linz Edition 5 Exercise 8.1 Question 7(e) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L= \{a^nb^jc^k:n<j,n\leq k \leq j\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
275
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
173
Peter Linz Edition 5 Exercise 8.1 Question 7(d) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L=\{a^nb^jc^k : k>n,k>j\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
187
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
2
answers
174
Peter Linz Edition 5 Exercise 8.1 Question 7(c) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^jc^k:k=jn\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
455
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
175
Peter Linz Edition 5 Exercise 8.1 Question 7(b) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j: n\geq(j-1)^3\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
144
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
1
vote
0
answers
176
Peter Linz Edition 5 Exercise 8.1 Question 7(a) (Page No. 212)
Show that the following languages on $\Sigma = \{a,b,c\}$ are not context-free. $L = \{a^nb^j : n\leq j^2\}$.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
280
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
177
Peter Linz Edition 5 Exercise 8.1 Question 6 (Page No. 212)
Show that the language $L = \Big\{ a^{n^2} :n\geq 0\Big\}$ is not context free.
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
301
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
proof
context-free-language
0
votes
0
answers
178
Peter Linz Edition 5 Exercise 8.1 Question 5 (Page No. 212)
Is the language $L = \{a^nb^m:n=2^m\}$ context free$?$
Rishi yadav
asked
in
Theory of Computation
Apr 15, 2019
by
Rishi yadav
242
views
peter-linz
peter-linz-edition5
theory-of-computation
pumping-lemma
context-free-language
0
votes
0
answers
179
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$}.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 14, 2019
by
Naveen Kumar 3
139
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
0
votes
0
answers
180
Peter Linz Edition 4 Exercise 5.1 Question 25 (Page No. 135)
Prove that if $G$ is a context-free grammar, then every $w ∈ L(G)$ has a leftmost and rightmost derivation. Give an algorithm for finding such derivations from a derivation tree.
Naveen Kumar 3
asked
in
Theory of Computation
Apr 14, 2019
by
Naveen Kumar 3
155
views
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
21
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-language
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:...