Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged regular-language
0
votes
0
answers
151
Michael Sipser Edition 3 Exercise 1 Question 41 (Page No. 89)
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},$ where $a_{1} · · · a_{k} ∈ A$ and $b_{1} · · · b_{k} ∈ B,$ each $a_{i}, b_{i} ∈ Σ$}}.$ Show that the class of regular languages is closed under perfect shuffle.
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},$ where $a_{1} · · · a_{k} ∈...
admin
451
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
perfect-shuffle
+
–
0
votes
0
answers
152
Michael Sipser Edition 3 Exercise 1 Question 40 (Page No. 89)
Recall that string $x$ is a $\text{prefix}$ of string $y$ if a string $z$ exists where $xz = y,$ and that $x$ is a $\text{proper prefix}$ of $y$ if in addition $x\neq y.$ In each of the following parts, we define an operation on a ... $\text{NOEXTEND(A) = {w ∈ A| w is not the proper prefix of any string in A}.}$
Recall that string $x$ is a $\text{prefix}$ of string $y$ if a string $z$ exists where $xz = y,$ and that $x$ is a $\text{proper prefix}$ of $y$ if in addition $x\neq y.$...
admin
354
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
prefix-free-property
+
–
0
votes
1
answer
153
Michael Sipser Edition 3 Exercise 1 Question 38 (Page No. 89)
An $\text{all-NFA}$ $M$ is a $\text{5-tuple}$ $(Q, Σ, δ, q_{0}, F)$ that accepts $x\in\sum^{*}$ if every possible state that $M$ could be in after reading input $x$ is a state from $F.$ Note ... string if some state among these possible states is an accept state$.$ Prove that $\text{all-NFAs}$ recognize the class of regular languages$.$
An $\text{all-NFA}$ $M$ is a $\text{5-tuple}$ $(Q, Σ, δ, q_{0}, F)$ that accepts $x\in\sum^{*}$ if every possible state that $M$ could be in after reading input $x$ is...
admin
1.9k
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
1
answer
154
Michael Sipser Edition 3 Exercise 1 Question 37 (Page No. 89)
Let $C_{n} = \{x| x \text{ is a binary number that is a multiple of $n$}\}.$ Show that for each $n\geq1,$ the language $C_{n}$ is regular$.$
Let $C_{n} = \{x| x \text{ is a binary number that is a multiple of $n$}\}.$ Show that for each $n\geq1,$ the language $C_{n}$ is regular$.$
admin
932
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
2
answers
155
Michael Sipser Edition 3 Exercise 1 Question 36 (Page No. 89)
Let $B_{n} = \{a^{k}| \text{$k$ is a multiple of $n$}\}.$ Show that for each $n\geq 1,$ the language $B_{n}$ is regular$.$
Let $B_{n} = \{a^{k}| \text{$k$ is a multiple of $n$}\}.$ Show that for each $n\geq 1,$ the language $B_{n}$ is regular$.$
admin
382
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
156
Michael Sipser Edition 3 Exercise 1 Question 35 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of $0's$ ... $ is the reverse of the top row of $w$}\}.$ Show that $E$ is not regular$.$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
176
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
157
Michael Sipser Edition 3 Exercise 1 Question 34 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns of ... $\begin{bmatrix} 0\\0 \end{bmatrix}\notin D$ Show that $D$ is regular$.$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
228
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
158
Michael Sipser Edition 3 Exercise 1 Question 33 (Page No. 89)
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}\end{Bmatrix}.$ Here $\sum_{2}$ contains all columns ... $C$ is regular. $\text{(You may assume the result claimed in question $31$})$
Let $\sum_{2}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \end{bmatrix},\begin{bmatrix} 0\\1 \end{bmatrix},\begin{bmatrix} 1 \\0 \end{bmatrix},\begin{bmatrix} 1 \\1 \end{bmatrix}...
admin
252
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
1
votes
0
answers
159
Michael Sipser Edition 3 Exercise 1 Question 32 (Page No. 88)
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix}, .,\begin{bmatrix} 1\\1 \\1 \end{bmatrix}\end{Bmatrix}.$ $\sum_{3}$ ... $B$ is regular. $\text{(Hint$:$Working with $B^{R}$ is easier. You may assume the result claimed in question $31$})$
Let $\sum_{3}=\begin{Bmatrix}\begin{bmatrix} 0\\0 \\0 \end{bmatrix},\begin{bmatrix} 0\\0 \\1 \end{bmatrix},\begin{bmatrix} 0\\1 \\0 \end{bmatrix},…….,\begin{bmatrix} ...
admin
483
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
160
Michael Sipser Edition 3 Exercise 1 Question 31 (Page No. 88)
For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,$ let $A^{R} = \{w^{R}| w\in A\}.$ Show that if $A$ is regular$,$ so is $A^{R}.$
For any string $w = w_{1}w_{2} · · · w_{n},$ the reverse of $w,$ written $w^{R},$ is the string $w$ in reverse order$, w_{n} · · · w_{2}w_{1}.$ For any language $A,...
admin
307
views
admin
asked
Apr 28, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
1
votes
1
answer
161
Michael Sipser Edition 3 Exercise 1 Question 29 (Page No. 88)
Use the pumping lemma to show that the following languages are not regular. $A_{1}=\{0^{n}1^{n}2^{n}|n\geq 0\}$ $A_{2}=\{www|w\in\{a,b\}^{*}\}$ $A_{3}=\{a^{{2}^{n}}|n\geq 0\}$ $\text{(Here,}$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$
Use the pumping lemma to show that the following languages are not regular.$A_{1}=\{0^{n}1^{n}2^{n}|n\geq 0\}$$A_{2}=\{www|w\in\{a,b\}^{*}\}$$A_{3}=\{a^{{2}^{n}}|n\geq 0\...
admin
2.9k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
pumping-lemma
+
–
0
votes
0
answers
162
Michael Sipser Edition 3 Exercise 1 Question 23 (Page No. 87)
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$
Let $B$ be any language over the alphabet $Σ.$ Prove that $B = B^{+}$ iff $BB ⊆ B.$
admin
531
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
proof
+
–
1
votes
1
answer
163
Michael Sipser Edition 3 Exercise 1 Question 20 (Page No. 86)
For each of the following languages, give two strings that are members and two strings that are not members-a total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts. $a^{*}b^{*}$ $a(ba)^{*}b$ ... $aba\cup bab$ $(\epsilon\cup a)b$ $(a\cup ba\cup bb)\Sigma^{*}$
For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the alphabet $...
admin
2.1k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
regular-language
regular-expression
+
–
0
votes
0
answers
164
Michael Sipser Edition 3 Exercise 1 Question 15 (Page No. 85)
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation$.$ Let $N_{1} = (Q_1, Σ, δ_1, q_1, F_1)$ ... , $N1,$ for which the constructed automaton $N$ does not recognize the star of $N_{1}^{'s}$ language.
Give a counterexample to show that the following construction fails to prove $\text{Theorem 1.49,}$ the closure of the class of regular languages under the star operation...
admin
1.0k
views
admin
asked
Apr 21, 2019
Theory of Computation
michael-sipser
theory-of-computation
finite-automata
regular-language
+
–
0
votes
0
answers
165
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
124
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
166
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
218
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
167
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
150
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
168
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
378
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
169
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
380
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
170
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
187
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 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
214
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 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
285
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
173
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
151
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 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
160
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
175
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
113
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
176
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
296
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
177
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
302
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
178
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
276
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
179
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
372
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
regular-language
pumping-lemma
+
–
0
votes
1
answer
180
Peter Linz Edition 4 Exercise 4.3 Question 12 (Page No. 123)
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Apply the pumping lemma to show that $L=$ {$a^nb^kc^{n+k}:n\geq0,k\geq0$} is not regular.
Naveen Kumar 3
240
views
Naveen Kumar 3
asked
Apr 11, 2019
Theory of Computation
peter-linz
peter-linz-edition4
theory-of-computation
pumping-lemma
regular-language
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
10
11
...
24
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register