Dark Mode

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

136 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

192 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

139 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

188 views

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).

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

137 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

118 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

99 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

164 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

307 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

664 views

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$.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

192 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

92 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

113 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

125 views

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.$

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

168 views

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$

Naveen Kumar 3 asked in Theory of Computation Apr 13, 2019

by Naveen Kumar 3

135 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

160 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

116 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

262 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

224 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

131 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

137 views

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$}$^+$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

145 views

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|$}

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

108 views

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∈Σ^+$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

122 views

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?

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

79 views

1 vote

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

205 views

0 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$}

Naveen Kumar 3 asked in Theory of Computation Apr 12, 2019

by Naveen Kumar 3

223 views

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$}.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

227 views

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.

Naveen Kumar 3 asked in Theory of Computation Apr 11, 2019

by Naveen Kumar 3

185 views

Page:

« prev
1
2
3
4
5
6
7
8
9
10
11
...
20
next »

Recent questions tagged peter-linz