Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged peter-linz
0
votes
1
answer
151
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 context-free.
Show that the complement of the language $L=$ {$ww^R:w∈$ {$a,b$}$^*$} is context-free.
Naveen Kumar 3
204
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
152
Peter Linz Edition 4 Exercise 5.1 Question 15 (Page No. 134)
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.
Show that the following language is context-free. $L=$ {$uvwv^R:u,v,w∈$ {$a,b$}$^+,|u|=|w|=2$}.
Naveen Kumar 3
326
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
153
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 context-free language.
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 context-free ...
Naveen Kumar 3
296
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
1
answer
154
Peter Linz Edition 4 Exercise 5.1 Question 13 (Page No. 134)
Let $L =$ {$a^nb^n : n ≥ 0$}. (a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134 (b) Show that $L^k$ is context-free for any given $k ≥ 1$. (c) Show that $\overline{L}$ and $L^*$ are context-free.
Let $L =$ {$a^nb^n : n ≥ 0$}.(a) https://gateoverflow.in/305106/peter-linz-edition-4-exercise-5-1-question-13-a-page-no-134(b) Show that $L^k$ is context-free for any g...
Naveen Kumar 3
339
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
155
Peter Linz Edition 4 Exercise 5.1 Question 12 (Page No. 134)
Given a context-free grammar $G$ for a language $L$, show how one can create from $G$ a grammar $\widehat{G}$ so that $L(\widehat{G}$) = head (L).
Given a context-free grammar $G$ for a language $L$, show how one can create from $G$ a grammar $\widehat{G}$ so that $L(\widehat{G}$) = head (L).
Naveen Kumar 3
189
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
156
Peter Linz Edition 4 Exercise 5.1 Question 11 (Page No. 134)
Find a context-free grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
Find a context-free grammar for $Σ =$ {$a, b$} for the language $L =$ {$a^nww^Rb^n : w ∈ Σ^*, n ≥ 1$}.
Naveen Kumar 3
199
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
157
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.
Find a context-free grammar for $head (L)$, where $L$ is the language $L =$ {$a^nb^m : n ≤ m + 3$}. Forthe definition of $head$ see Exercise 18, Section 4.1.
Naveen Kumar 3
245
views
Naveen Kumar 3
asked
Apr 14, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
158
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.
Show that $L =$ {$w ∈$ {$a,b,c$}$^* : |w| = 3n_a(w)$} is a context-free language.
Naveen Kumar 3
312
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
4
answers
159
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$}.
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 $...
Naveen Kumar 3
422
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
context-free-language
+
–
0
votes
6
answers
160
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$}.
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$}.(c) https://gateo...
Naveen Kumar 3
944
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-language
context-free-grammar
+
–
0
votes
0
answers
161
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$.
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.1Let $G = (V, T, S, ...
Naveen Kumar 3
266
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
162
Peter Linz Edition 4 Exercise 5.1 Question 5 (Page No. 133)
Is the language $L(G)=$ {$ab(bbaa)^nbba(ba)^n:n\geq0$} regular?
Is the language $L(G)=$ {$ab(bbaa)^nbba(ba)^n:n\geq0$} regular?
Naveen Kumar 3
130
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
163
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$}.
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),$ w...
Naveen Kumar 3
201
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
2
votes
0
answers
164
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.
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 d...
Naveen Kumar 3
178
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
165
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.$
Draw the derivation tree corresponding to the derivation in Example 5.1.Example 5.1The grammar $G = (${$S$}, {$a, b$}$, S, P),$ with productions$S\rightarrow aSa$$S\right...
Naveen Kumar 3
216
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
1
answer
166
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$
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
190
views
Naveen Kumar 3
asked
Apr 13, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
context-free-grammar
+
–
0
votes
0
answers
167
Peter Linz Edition 4 Exercise 4.3 Question 26 (Page No. 124)
Let $L=$ {$a^nb^m:n\geq100,m\leq50$}. (a) Can you use the pumping lemma to show that L is regular? (b) Can you use the pumping lemma to show that L is not regular? Explain your answers.
Let $L=$ {$a^nb^m:n\geq100,m\leq50$}.(a) Can you use the pumping lemma to show that L is regular?(b) Can you use the pumping lemma to show that L is not regular?Explain y...
Naveen Kumar 3
233
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
0
votes
0
answers
168
Peter Linz Edition 4 Exercise 4.3 Question 25 (Page No. 124)
In the chain code language in Exercise 24, Section 3.1, let $L$ be the set of all $w ∈$ {$u,r,l,d$}$^*$ that describe rectangles. Show that $L$ is not a regular language.
In the chain code language in Exercise 24, Section 3.1, let $L$ be the set of all $w ∈$ {$u,r,l,d$}$^*$ that describe rectangles. Show that $L$ is not a regular languag...
Naveen Kumar 3
154
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
2
answers
169
Peter Linz Edition 4 Exercise 4.3 Question 24 (Page No. 124)
Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude from this that $L_2$ is regular?
Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude from this that $L_2$ is regular?
Naveen Kumar 3
397
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
2
answers
170
Peter Linz Edition 4 Exercise 4.3 Question 23 (Page No. 124)
Is the family of regular languages closed under infinite intersection?
Is the family of regular languages closed under infinite intersection?
Naveen Kumar 3
408
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
0
answers
171
Peter Linz Edition 4 Exercise 4.3 Question 22 (Page No. 124)
Consider the argument that the language associated with any generalized transition graph is regular. The language associated with such a graph is $L=\bigcup_{p∈P} L(r_p)$, where $P$ ... is regular. Show that in this case, because of the special nature of $P$, the infinite union is regular.
Consider the argument that the language associated with any generalized transition graph is regular. The language associated with such a graph is $L=\bigcu...
Naveen Kumar 3
201
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
0
answers
172
Peter Linz Edition 4 Exercise 4.3 Question 21 (Page No. 124)
Let $P$ be an infinite but countable set, and associate with each $p ∈ P$ a language $L_p$. The smallest set containing every $L_p$ is the union over the infinite set $P$; it will be denoted by $U_{p∈p}L_p$. Show by example that the family of regular languages is not closed under infinite union.
Let $P$ be an infinite but countable set, and associate with each $p ∈ P$ a language $L_p$. The smallest set containing every $L_p$ is the union over the infinite set $...
Naveen Kumar 3
218
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
closure-property
+
–
0
votes
0
answers
173
Peter Linz Edition 4 Exercise 4.3 Question 20 (Page No. 124)
Is the following language regular? $L=$ {$ww^Rv:v,w∈$ {$a,b$}$^+$}.
Is the following language regular? $L=$ {$ww^Rv:v,w∈$ {$a,b$}$^+$}.
Naveen Kumar 3
293
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
174
Peter Linz Edition 4 Exercise 4.3 Question 19 (Page No. 124)
Are the following languages regular? (a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$} (b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Are the following languages regular?(a) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$}(b) $L=$ {$uww^Rv:u,v,w∈ ${$a,b$}$^+$, $|u|\geq |v|$}
Naveen Kumar 3
160
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
0
votes
0
answers
175
Peter Linz Edition 4 Exercise 4.3 Question 18 (Page No. 124)
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Apply the pigeonhole argument directly to the language in $L=$ {$ww^R:w∈Σ^+$}.
Naveen Kumar 3
167
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pigeonhole-principle
+
–
0
votes
0
answers
176
Peter Linz Edition 4 Exercise 4.3 Question 17 (Page No. 124)
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Let $L_1$ and $L_2$ be regular languages. Is the language $L =$ {$w : w ∈ L_1, w^R ∈ L_2$ necessarily regular?
Naveen Kumar 3
117
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
+
–
1
votes
1
answer
177
Peter Linz Edition 4 Exercise 4.3 Question 16 (Page No. 123)
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
Is the following language regular? $L=$ {$w_1cw_2:w_1,w_2∈$ {$a,b$}$^*,w_1\neq w_2$}.
Naveen Kumar 3
325
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
1
votes
0
answers
178
Peter Linz Edition 4 Exercise 4.3 Question 15 (Page No. 123)
Consider the languages below. For each, make a conjecture whether or not it is regular. Then prove your conjecture. (a) $L=$ {$a^nb^la^k:n+k+l \gt 5$} (b) $L=$ {$a^nb^la^k:n \gt 5,l> 3,k\leq l$} (c) $L=$ {$a^nb^l:n/l$ is an integer} (d) $L=$ ... $L=$ {$a^nb^l:n\geq 100,l\leq 100$} (g) $L=$ {$a^nb^l:|n-l|=2$}
Consider the languages below. For each, make a conjecture whether or not it is regular. Thenprove your conjecture.(a) $L=$ {$a^nb^la^k:n+k+l \gt 5$}(b) $L=$ {$a^nb^la^k:n...
Naveen Kumar 3
312
views
Naveen Kumar 3
asked
Apr 12, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
closure-property
+
–
0
votes
1
answer
179
Peter Linz Edition 4 Exercise 4.3 Question 13 (Page No. 123)
Show that the following language is not regular. $L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
Show that the following language is not regular.$L=$ {$a^nb^k:n>k$} $\cup$ {$a^nb^k:n\neq k-1$}.
Naveen Kumar 3
285
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
closure-property
+
–
0
votes
1
answer
180
Peter Linz Edition 4 Exercise 4.3 Question 14 (Page No. 123)
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ is also non regular.
Prove or disprove the following statement: If $L_1$ and $L_2$ are non regular languages, then $L_1 ∪ L_2$ isalso non regular.
Naveen Kumar 3
395
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
20
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register