Register

Recent questions tagged regular-language

213
views
0 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 45 (Page No. 90)
Let $\text{A/B = {w| wx ∈ A for some x ∈ B}}.$ Show that if $A$ is regular and $B$ is any language, then $\text{A/B}$ is regular.
User Avatar
214
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 44 (Page No. 90)
Let $B$ and $C$ be languages over $\sum = \{0, 1\}.$ Define $B\overset{1}{\leftarrow} C = \{w\in B|$ $\text{for some}$ $y\in C$ ... $\overset{1}{\leftarrow}$operation.
User Avatar
710
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 43 (Page No. 90)
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ ... picture and a more formal proof by construction as in $\text{Theorem 1.47.}$
User Avatar
361
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 42 (Page No. 89)
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},$ ... $a_{i}, b_{i} ∈ Σ^{*}\}.$Show that the class of regular languages is closed under shuffle.
User Avatar
506
views
0 answers
0 votes
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_{i}, b_{i} ∈ Σ$}}.$Show that the class of regular languages is closed under perfect shuffle.
User Avatar
389
views
0 answers
0 votes
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 ...
User Avatar
2.1k
views
1 answers
0 votes
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$ ... states is an accept state$.$ Prove that $\text{all-NFAs}$ recognize the class of regular languages$.$
User Avatar
1.1k
views
1 answers
0 votes
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$.$
User Avatar
433
views
2 answers
0 votes
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$.$
User Avatar
186
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 35 (Page No. 89)
Let ... $}\}.$Show that $E$ is not regular$.$
User Avatar
251
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 34 (Page No. 89)
Let ... $\begin{bmatrix} 0\\0 \end{bmatrix}\notin D$Show that $D$ is regular$.$
User Avatar
274
views
0 answers
0 votes
Michael Sipser Edition 3 Exercise 1 Question 33 (Page No. 89)
Let ... $C$ is regular. $\text{(You may assume the result claimed in question $31$})$
User Avatar
531
views
0 answers
1 votes
Michael Sipser Edition 3 Exercise 1 Question 32 (Page No. 88)
Let ... $Working with $B^{R}$ is easier. You may assume the result claimed in question $31$})$
User Avatar
340
views
0 answers
0 votes
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,$ ... $A$ is regular$,$ so is $A^{R}.$
User Avatar
3.2k
views
1 answers
1 votes
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\}$ ... {(Here,}$\text{$a^{{2}^{n}}$}$ $\text{means a strings of $2^{n}$ a's.)}$
User Avatar
563
views
0 answers
0 votes
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.$
User Avatar
2.3k
views
1 answers
1 votes
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 ... $aba\cup bab$(\epsilon\cup a)b$(a\cup ba\cup bb)\Sigma^{*}$
User Avatar
1.1k
views
1 answers
1 votes
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$.$ ... $N$ does not recognize the star of $N_{1}^{'s}$ language.
User Avatar
145
views
0 answers
0 votes
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?
User Avatar
266
views
0 answers
0 votes
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.
User Avatar
187
views
0 answers
0 votes
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.
User Avatar
432
views
2 answers
0 votes
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?
User Avatar
451
views
2 answers
0 votes
Peter Linz Edition 4 Exercise 4.3 Question 23 (Page No. 124)
Is the family of regular languages closed under infinite intersection?
User Avatar
227
views
0 answers
0 votes
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 ... case, because of the special nature of $P$, the infinite union is regular.
User Avatar
231
views
0 answers
0 votes
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 ... . Show by example that the family of regular languages is not closed under infinite union.
User Avatar
306
views
0 answers
0 votes
Peter Linz Edition 4 Exercise 4.3 Question 20 (Page No. 124)
Is the following language regular? $L=$ {$ww^Rv:v,w∈$ {$a,b$}$^+$}.
User Avatar
186
views
0 answers
0 votes
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|$}
User Avatar
182
views
0 answers
0 votes
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∈Σ^+$}.
User Avatar
126
views
0 answers
0 votes
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?
User Avatar
341
views
1 answers
1 votes
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$}.
User Avatar
Page: