Give an nfa with minimum number of states for the following

Question

1. State whether the following statements are true or not. You must give a BRIEF explanation or show a counter example to receive full credit.

(a) If a subset of a regular language is regular then all of its subsets are regular.

(b) (0111 + 1011 + 1101 + 1110)* is the regular expression for the set of all strings with 3n₀ = n₁ where n₀ and n₁ respectively denote the numbers of 0s and 1s in w.

(c) Let R₁ = aba⁺ and R₂ = ab⁺a be two regular expressions then R₁ ∪ R₂ = ab(a + b)*b.

(d) With pumping lemma, we can prove that L = {w : w = 1000} is a regular language.

2. The following table shows a non-associative operation closed under set A = {a, b, c, d} The left-to-right and right-to-left evaluation values of a string w, when interpreted as an expression, are represented as wlr and wrl, respectively. As an example if w = adb then w_lr = (ad)b = ab = c and w_rl = a(db) = ac = b.

(a) Give a DFA for the following language with the alphabet A, the first input to the DFA will be the left-most letter of the string:

 

L = {ω : ω ∈ A*, ω_lr = d }

(b) Give an NFA with minimum number of states for the following language with the alphabet A, the first input to the NFA will be the left-most letter of the string:

L = {ω : ω ∈ A*, ω_rl = d }

3. Give a regular expression for the set of all strings from f0, 1g , which are base 2 represen-tations of a number which is a multiple of 5. For example, the string 1111 which represents (1111)2 and equals 15, must be generated by the regular expression since it is a multiple of 5.

4. If L is a regular language prove that the following languages are also regular.

5. Prove or disprove that the following languages are regular.