Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged context-free-language
0
votes
0
answers
91
Michael Sipser Edition 3 Exercise 2 Question 56 (Page No. 160)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ ... an accept state, it pretends that $c's$ are $b's$ in the input from that point on. What language would the modified $P$ accept?)
Let $A = L(G_{1})$ where $G_{1}$ is defined in Question $2.55$. Show that $A$ is not a DCFL.(Hint: Assume that $A$ is a DCFL and consider its DPDA $P$. Modify $P$ so that...
admin
188
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
0
votes
1
answer
92
Michael Sipser Edition 3 Exercise 2 Question 53 (Page No. 159)
Show that the class of DCFLs is not closed under the following operations: Union Intersection Concatenation Star Reversal
Show that the class of DCFLs is not closed under the following operations:UnionIntersectionConcatenationStarReversal
admin
311
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
0
answers
93
Michael Sipser Edition 3 Exercise 2 Question 50 (Page No. 159)
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz| xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
We defined the $CUT$ of language $A$ to be $CUT(A) = \{yxz| xyz \in A\}$. Show that the class of $CFLs$ is not closed under $CUT$.
admin
208
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
1
answer
94
Michael Sipser Edition 3 Exercise 2 Question 49 (Page No. 159)
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.
admin
1.3k
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
closure-property
descriptive
+
–
0
votes
0
answers
95
Michael Sipser Edition 3 Exercise 2 Question 48 (Page No. 159)
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $1s$ ... $C_{1}$ is a CFL. Show that $C_{2}$ is not a CFL.
Let $\Sigma = \{0,1\}$. Let $C_{1}$ be the language of all strings that contain a $1$ in their middle third. Let $C_{2}$ be the language of all strings that contain two $...
admin
283
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
descriptive
+
–
0
votes
0
answers
96
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
admin
227
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
0
answers
97
Michael Sipser Edition 3 Exercise 2 Question 43 (Page No. 158)
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ ... a regular language is context free. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ and $w4 have the same sy...
admin
278
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
0
answers
98
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Si...
admin
162
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
proof
+
–
0
votes
0
answers
99
Michael Sipser Edition 3 Exercise 2 Question 41 (Page No. 158)
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$. Show that the class of CFLs is not closed under NOPREFIX. Show that the class of CFLs is not closed under NOEXTEND.
Read the definitions of NOPREFIX(A) and NOEXTEND(A) in Question $1.40$.Show that the class of CFLs is not closed under NOPREFIX.Show that the class of CFLs is not closed ...
admin
255
views
admin
asked
Oct 12, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
+
–
0
votes
0
answers
100
Michael Sipser Edition 3 Exercise 2 Question 40 (Page No. 158)
Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefix-closed, context-free language. Show that $C$ contains an infinite regular subset.
Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let $C$ be an infinite, prefix-closed, context-free languag...
admin
219
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
+
–
0
votes
0
answers
101
Michael Sipser Edition 3 Exercise 2 Question 39 (Page No. 158)
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ where $ a_{1} · · · a_{k} ∈ A $ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ^{*}\}.$ Show that the class of context-free languages is not closed under shuffle.
For the definition of the shuffle operation. For languages $A$ and $B,$ let the $\text{shuffle}$ of $A$ and $B$ be the language $\{w| w = a_{1}b_{1} \ldots a_{k}b_{k},$ ...
admin
249
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
shuffle
+
–
0
votes
0
answers
102
Michael Sipser Edition 3 Exercise 2 Question 38 (Page No. 158)
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language $\text{{$w| w = a_{1}b_{1} · · · a_{k}b_{k},$ ... k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of context-free languages is not closed under perfect shuffle.
For the definition of the perfect shuffle operation. For languages $A$ and $B,$ let the $\text{perfect shuffle}$ of $A$ and $B$ be the language$\text{{$w| w = a_{1}b_{1} ...
admin
238
views
admin
asked
Oct 10, 2019
Theory of Computation
michael-sipser
theory-of-computation
context-free-language
perfect-shuffle
+
–
2
votes
3
answers
103
CMI2019-A-1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$The language $L_{1}\cup L_{2}$ is:regular...
gatecse
845
views
gatecse
asked
Sep 13, 2019
Theory of Computation
cmi2019
regular-language
context-free-language
closure-property
+
–
1
votes
0
answers
104
Ullman (TOC) Edition 3 Exercise 9.5 Question 3 (Page No. 418 - 419)
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but that is not the same thing. To prove our initial ... ;s lemma to force equality in the lengths of certain substrings as in the hint to Exercise $7.2.5(b)$.
It is undecidable whether the complement of a CFL is also a CFL. Exercise $9.5.2$ can be used to show it is undecidable whether the complement of a CFL is regular, but th...
admin
343
views
admin
asked
Jul 26, 2019
Theory of Computation
ullman
theory-of-computation
context-free-language
pcp
descriptive
+
–
2
votes
1
answer
105
UGC NET CSE | June 2019 | Part 2 | Question: 77
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite? By constructing redundant CFG G in CNF generating language $L$ By constructing non-redundant CFG G in CNF generating language $L$ By constructing non- ... for null) Which of the following is correct? i only ii only iii only None of i, ii and iii
How can the decision algorithm be constructed for deciding whether context-free language $L$ is finite?By constructing redundant CFG G in CNF generating language $L$By co...
Arjun
1.5k
views
Arjun
asked
Jul 2, 2019
Theory of Computation
ugcnetcse-june2019-paper2
context-free-language
+
–
1
votes
0
answers
106
Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are context-free. (a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*} (b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}. (C) $L=$ {$a^nb^ja^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.
Determine whether or not the following languages are context-free.(a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*}(b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}.(C) $L=$ {...
Naveen Kumar 3
693
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
pumping-lemma
proof
+
–
2
votes
2
answers
107
Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?
Is the language L = {$a^nb^m : n = 2^m$} context-free?
Naveen Kumar 3
557
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
1
votes
2
answers
108
Peter Linz Edition 4 Exercise 8.1 Question 1 (Page No. 212)
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
Show that the language $L=${$a^nb^nc^m,n\neq m$} is not context-free.
Naveen Kumar 3
480
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
context-free-language
+
–
0
votes
0
answers
109
Peter Linz Edition 4 Exercise 7.4 Question 9 (Page No. 204)
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}. (i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} . (ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} . (iii) $L=$ {$a^nb^{n+2}c^{m}:n\geq0,m\gt1$} . (iv) $L=$ {$w:n_a(w)\lt n_b(w)$} . (v) $L=$ {$w:n_a(w)+n_b(w)\neq n_c(w)$} .
Give LL grammars for the following languages, assuming $Σ =$ {$a,b, c$}.(i) $L=$ {$a^nb^mc^{n+m}:n\geq0,m\geq0$} .(ii) $L=$ {$a^{n+2}b^mc^{n+m}:n\geq0,m\geq0$} .(iii) $L...
Naveen Kumar 3
377
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
0
answers
110
Peter Linz Edition 4 Exercise 7.4 Question 7 (Page No. 204)
Show that a deterministic context-free language is never inherently ambiguous.
Show that a deterministic context-free language is never inherently ambiguous.
Naveen Kumar 3
219
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
inherently-ambiguous
+
–
0
votes
0
answers
111
Peter Linz Edition 4 Exercise 7.4 Question 6 (Page No. 204)
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
Show that if G is an LL (k) grammar, then L (G) is a deterministic context-free language.
Naveen Kumar 3
251
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
112
Peter Linz Edition 4 Exercise 7.4 Question 5 (Page No. 204)
Show that any LL grammar is unambiguous.
Show that any LL grammar is unambiguous.
Naveen Kumar 3
201
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
113
Peter Linz Edition 4 Exercise 7.4 Question 4 (Page No. 204)
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
Construct an LL grammar for the language L (a*ba) ∪ L (abbb*).
Naveen Kumar 3
267
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
0
answers
114
Peter Linz Edition 4 Exercise 7.4 Question 3 (Page No. 204)
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
Find an LL grammar for the language L = {$w : n_a (w) = n_b (w)$}.
Naveen Kumar 3
166
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
115
Peter Linz Edition 4 Exercise 7.4 Question 2 (Page No. 204)
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
Show that the grammar for L = {$w : n_a (w) = n_b (w)$} which is, $S\rightarrow SS,S\rightarrow \lambda,S\rightarrow aSb,S\rightarrow bSa$ is not an LL grammar.
Naveen Kumar 3
255
views
Naveen Kumar 3
asked
Jun 25, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
0
answers
116
Peter Linz Edition 4 Exercise 7.3 Question 18 (Page No. 200)
Give an example of a deterministic context-free language whose reverse is not deterministic.
Give an example of a deterministic context-free language whose reverse is not deterministic.
Naveen Kumar 3
428
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
117
Peter Linz Edition 4 Exercise 7.3 Question 17 (Page No. 200)
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.
Show that under the conditions of Exercise 16, $L_1 ∩ L_2$ is a deterministic context-free language.
Naveen Kumar 3
220
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
118
Peter Linz Edition 4 Exercise 7.3 Question 16 (Page No. 200)
Show that if $L_1$ is deterministic context-free and $L_2$ is regular, then the language $L_1 ∪ L_2$ is deterministic context-free.
Show that if $L_1$ is deterministic context-free and $L_2$ is regular, then the language $L_1 ∪ L_2$ isdeterministic context-free.
Naveen Kumar 3
330
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
1
answer
119
Peter Linz Edition 4 Exercise 7.3 Question 15 (Page No. 200)
Show that every regular language is a deterministic context-free language.
Show that every regular language is a deterministic context-free language.
Naveen Kumar 3
227
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
0
votes
0
answers
120
Peter Linz Edition 4 Exercise 7.3 Question 11 (Page No. 200)
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic context-free language.
Show that $L =$ {$w ∈$ {$a, b$}$^* : n_a (w) ≠ n_b (w)$} is a deterministic context-free language.
Naveen Kumar 3
160
views
Naveen Kumar 3
asked
Jun 23, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
...
21
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register