Reference no: EM132239472
Computability, Automata, and Formal Languages Assignment -
Background on GNFAs:
A GNFA (generalized NFA) is an NFA that has the following properties (you can read more about these in Section 1.4 of the Sipser book):
(a) Each transition is labeled with a regular expression, not just a single symbol
(b) The initial state qinitial has no transitions leading to it
(c) There is only one final state qaccept.
(d) qaccept has no transitions leaving it.
(e) Let q be a state other than qaccept, and let q' be a state other than qinitial. Then there is a transition from q to q'.
GNFAs are an important part of proving that for every regular language, some regular expression describes it.
Assignment -
1. Use the given procedure to find a regular expression that describes the language of M2 from the previous homework, depicted below.
(a) Construct a GNFA (call it N0) for this machine following rules (a)-(e) above. That is, add a new initial state, a new accept state, and connect all intermediate states to one another with transitions labeled with regular expressions. Your GNFA should have 5 states, and each state (other than the accept state) should have 4 outgoing transitions (any transition labeled with the ∅ means it's a transition that didn't exist in the original machine).
(b) What is the GNFA that results from ripping state q1 out of N0? Call this machine N1.
(c) What is the GNFA that results from ripping state q2 out of N1? Call this machine N2.
(d) What is the GNFA that results from ripping state q3 out of N2? Call this machine N3.
(e) Using N3, determine a regular expression that describes the language of the original DFA.
2. Write a regular expression describing each of the following languages, all over the alphabet {0, 1}.
(a) All even numbers represented in binary.
(b) The language of all strings satisfying this condition: if the string contains a 1, then it does not contain any 0's.
(c) The language of all strings satisfying this condition: if the string has length exactly 2, then it does not contain any 1's.
(d) Strings for which all 1's occur in pairs: that is, no 1 can be all by itself, and 111 is never a substring.
3. Suppose that A is regular and B is not regular. Is it possible for A ∪ B to be regular? (if it is possible, show an example - otherwise, prove that it is not possible using the pumping lemma or any other technique).
4. Suppose that A is regular and B is not regular. Is it possible for A o B to be regular? (if it is possible, show an example - otherwise, prove that it is not possible using the pumping lemma or any other technique).
5. Show that {www | w ∈ {0, 1}*} is not regular (you may use the pumping lemma or any other technique).
Attachment:- Assignment File.rar