Reference no: EM133008757

Question 1 We are using the alphabet {0, I}. We have a DFA with 5 states, S = {s₀, s₁, s₂, s₃, s₄}. The start state is so and the only accepting state is also so. The transitions are given by the formula

δ(s_i, a) = s_j where j = i² + a mod 5.

Draw the table showing which pairs of states are inequivalent and then construct the minimal automaton. Remember to remove useless states right from the start, before you draw the table. I am happy with a drawing of the automaton.

Question 2 Are the following statements true or false? Justify your answer in each case. We have some fixed alphabet Σ with at least two letters. In the following A and B stand for languages, i.e. subsets of Σ*
• If A is regular and A ⊆ B then B must be regular.
• If A and AB are both regular then B must be regular.
• If {Ai|i ∈ N) is an infinite family of regular sets then U^∞_i=1. j A_i is regular.
• If A is not regular it cannot have a regular subset. 15]

Question 3 Consider the language L = {aⁿb^m|n ≠ m); as we have seen this is not regular. Recall the definition of the equivalence ≡L which we used in the proof of the Myhill-Nerode theorem. Since this language is not regular ≡L, cannot have finitely many equivalence classes. Exhibit explicitly, infinitely many distinct equivalence classes of ≡L.

Question 4 Describe an algorithm that given two different regular expressions R₁ and R₂ decides whether R₁ ⊆ R₂. The description should be high-level and at the level of detail shown in the example I posted on the website. I will deduct marks for excessive low-level details and I will give you zero If you submit code.

Question 5 Let D be the language of words w such that w has an even number of a's and an odd number of b's and does not contain the substring

1. Give a DFA with only five states, including any dead states, that recognizes D.

2. Give a regular expression for this language.