search
Log In
0 votes
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.
in Theory of Computation 40 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
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\}$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 32 views
0 votes
0 answers
2
45 views
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.$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 45 views
0 votes
0 answers
3
44 views
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).$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 44 views
...