search
Log In
0 votes
83 views
Let $\sum = \{0,1\}$ and let $D = \{w|w$  $\text{contains an equal number of occurrences of the sub strings 01 and 10}\}.$
Thus $101\in D$ because $101$ contains a single $01$ and a single $10,$ but $1010\notin D$ because $1010$ contains two $10's$ and one $01.$ Show that $D$ is a regular language.
in Theory of Computation
edited by
83 views

Please log in or register to answer this question.

Related questions

0 votes
1 answer
1
90 views
Let $B=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at least}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $B$ is a regular language. Let $C=\{1^{k}y|y\in\{0,1\}^{*}$ $\text{ and y contains at most}$ $k$ $1's,$ $\text{for every}$ $k\geq 1\}.$ Show that $C$ isn’t a regular language.
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 90 views
0 votes
0 answers
2
282 views
Let $A$ be any language. Define $\text{DROP-OUT(A)}$ to be the language containing all strings that can be obtained by removing one symbol from a string in $A.$ Thus, $\text{DROP-OUT(A) = $\{xz| xyz\in A$ where $x, z\in\sum^{*},y\in\sum$\}}.$ Show ... is closed under the $\text{DROP-OUT}$ operation. Give both a proof by picture and a more formal proof by construction as in $\text{Theorem 1.47.}$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 282 views
0 votes
0 answers
3
44 views
Let $\sum=\{1,\#\}$ and let $Y=\{w|w=x_{1}\#x_{2}\#...\#x_{k}$ $\text{for}$ $k\geq 0,$ $\text{each}$ $ x_{i}\in 1^{*},$ $\text{and}$ $x_{i}\neq x_{j}$ $\text{for}$ $i\neq j\}.$ Prove that $Y$ is not regular.
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 44 views
0 votes
0 answers
4
121 views
Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection,and complement. $\{0^{n}1^{m}0^{n}|m,n\geq 0\}$ $\{0^{m}1^{n}|m\neq n\}$ $\{w|w\in\{0,1\}^{*} \text{is not a palindrome}\}$ $\{wtw|w,t\in\{0,1\}^{+}\}$
asked Apr 30, 2019 in Theory of Computation Lakshman Patel RJIT 121 views
...