Register

Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)

325 views
0 votes
0 votes

Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$

  1. Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $|s| < max(k1, k2).$
  2. Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $|s| < k1k2.$
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

2 votes
2 votes
2 answers
1
admin asked Apr 30, 2019
509 views
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
Let $\sum = \{0,1\}$Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular.Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}....
User Avatar
1 votes
1 votes
0 answers
4
admin asked Apr 30, 2019
335 views
Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states.Descri...
User Avatar
Link Copied!