# Ullman (TOC) Edition 3 Exercise 4.2 Question 14 (Page No. 149 - 150)

40 views

We described the $"$product construction$"$ that took two DFA's and constructed one DFA whose language is intersection of the languages of the first two.

1. Show how to perform the product construction on NFA's (without $\in$ transitions).
2. Show how to perform the product construction on $\in-$NFA's
3. Show how to modify the product construction so the resulting DFA accepts the difference of the languages of the two given DFA's.
4. Show how to modify the product construction so the resulting DFA accepts the union of the languages of the two given DFA's.

## Related questions

1
32 views
We can use closure properties to help prove certain languages are not regular. Start with the fact that the language $L_{0n1n}=\{0^{n}1^{n}|n\geq 0\}$ is not a regular set. Prove the following languages not to be regular by transforming them using operations known to preserve regularity,to $L_{0n1n}:$ $\{0^{i}1^{j}|i\neq j\}$ $\{0^{n}1^{m}2^{n-m}|n\geq m\geq 0\}$
Let $w_{1}=a_{0}a_{0}a_{1},$ and $w_{i}=w_{i-1}w_{i-1}a_{i}$ for all $i>1.$For instance,$w_{3}=a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{0}a_{0}a_{1}a_{0}a_{0}a_{1}a_{2}a_{3}.$ ... $O(n^{2}).$ Find such an expression. Hint $:$ Find $n$ languages, each with regular expressions of length $O(n).$ Whose intersection is $L.$
Show that the regular languages are closed under the following operation$:$ $\text{cycle(L)={we can write w as w = xy,such that yx is in L}}.$ For example if $L=\{01,011\},$then $cycle(L)=\{01,10,011,110,101\}.$ Hint$:$ Start with a DFA for $L$ and construct an $\in-NFA$ for $cycle(L).$
Suppose that $L$ is any language not necessarily regular whose alphabet is $\{0\};$i.e. the strings of $L$ consist of $0's$ only. Prove that $L^{*}$ is regular. Hint$:$ ... if $j$ is odd ,use copy of $000$ and $(j-3)/2$ copies of $00.$ Thus ,$L^{*}=$ $\in + 000^{*}.$