Reference no: EM132254976

Question 1. Construct a DFA equivalent to the following NFA.

	a		b	λ
→q0		Φ	Φ	{q1, q4}
q1*		{q2}	Φ	Φ
q2		Φ	{q3}	Φ
q3		Φ	{q1}	Φ
q4		{q4}	Φ	{q5}
q5*		Φ	{q6}	Φ
q6		{q5}	Φ	Φ

Question 2. Consider a water bottle vending machine as a finite-state automaton. This machine is designed to accept coins of Rs. 2 and 5 only. It dispenses a single water bottle as soon as the amount entered is equal to or greater than Rs. 12. Coins may be inserted in any order and the machine returns appropriate amounts of change (Note: it returns a chocolate in place of one rupee change). However, there is no cancel button to get back the coins without completing the transaction. What is the exact number of states needed in this automaton? Show the automaton.

Question 3. The DFA M accepts a Language L over some alphabet Σ with distinct start state qs and a single final state qf.
i) What happens to L(M) if we introduce the following transition?
δ(qs , x) = qs for ∀ x ?Σ
You may express this formally using set theoretic notations or precisely in English.
ii) Would the automaton be still a DFA? Why?

Question 4. Construct FSM for the following scenarios.
Input: non empty binary sequence
I) output:
Should end in a final state if the input stream has a 1. So your automaton should mimic OR operation.
ii) output:
Should end in a final state only if the input stream has only a sequence of 1 and no 0. So your automaton should mimic AND operation.

Question 5. Write a regular expression for the following language:
L = {w ? {0, 1}* | w contains an equal number of occurrences of the substring 01 and 10}
(Eg. 010 ? L because 010 contains a single 01 and a single 10 as substrings; but 01101 doesn't belong to L because 01101 contains two 01 s and one 10.

Question 6. Consider the finite automaton given by the diagram. Is this automaton deterministic? Using a standard method construct a regular expression for the language defined by the automaton.

Question 7. Minimize the DFA with the set of states {1, 2, 3, 4, 5, 6, 7, 8}, input alphabet Σ = {a, b} initial state 1, final states {3, 4} and the transition function given by the table:

Let L be the language accepted by this DFA. Consider the equivalence relation RL on Σ* (thus RL⊆Σ* × Σ*) defined by: xRLy if and only if for all z ∈Σ*, xz∈ L iffyz∈ L. What is the index (the number of equivalence classes) of RL? Describe precisely at least one of the equivalence classes of RL (by giving an automaton, or a regular expression).

Question 8. Find a regular expression for the language L = {w ? {a, b}*: n_a(w) is even &n_b(w) is odd}.

Question 9. Show that the language of binary strings of even length having the same number of 0s in its two halves is not regular.

Question 10. To show that Language containing equal number of a and b, can we select the string w as follows.
What could the adversary do in each case?
i) w = (ab)^m
ii) w = am^/2b^m/2