Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP2022/2922 Automata Conversions

S2 2023

After this tutorial you should be able to:

1. Remove ϵ-transitions from NFAs

2. Convert NFAs to DFAs

3. Convert DFAs to REs

4. Devise algorithms for solving certain decision problems about DFAs/NFAs

5. Show that certain languages are not regular.

Problem 1. In lectures we defined q ⇝ r for states q, r of an NFA to mean that there is a path from q to r labeled by zero or more ϵ-transitions. Write pseudo- code for a procedure silentmoves(q, r) that decides whether or not q ⇝ r.

Problem 2.[Exam 2020] Using the methods from the course, convert the regular expression a* nb into an NFA, and then remove its epsilon transitions. Show all the steps.

Problem 3.[Exam 2021] Consider the DFA M with states Q  =  {0, 1, 2},  Σ  = {a, b}, q0  = 0, F = {1}, and δ is as follows:

Give a short English description of L(M) and a regular expression for L(M). No additional justifications are needed.  (In the exam the question did not specify how this should be done;  in the tutorial, you should use the methods from lectures).

Problem 4.[Exam 2022] Describe in words the language recognised by the fol- lowing NFA (no additional justification is needed), and then give the DFA that results from applying the subset construction to the NFA:

You may draw or write the DFA, and no additional justification is needed. Note that you should only include the states in the DFA that are reachable from the initial state.

Algorithms

Problem 5. Consider the decision problem which takes as input a regular ex- pression R and string w, and outputs 1 if w  ∈  L(R), and 0 otherwise.  This problem is called the regular-expression membership problem.  In a previous tuto- rial we saw a recursive algorithm for solving this problem (called Match(R, w)). Using automata, we can give another algorithm.

1. Convert R into a DFA M such that L(R) = L(M).

2. Check if w ∈ L(M) using the algorithm for the DFA membership problem.

Does this algorithm run in polynomial time?

Problem 6. Consider the decision problem which takes as input regular expres- sions R1, R2, and outputs 1 if L(R1) = L(R2), and 0 otherwise.  This problem is called the regular-expression equivalence problem.  Give an algorithm that solves this decision problem. (Hint: use automata).

Showing a language is not regular

You may find the following terminology helpful.  For a language L, we say that two strings x and y are distinguished by L ifthere is a string z such that only one of xz and yz are in L (and in this case we say that z distinguishes x and y). To prove a language is not regular, you should find, for every N, strings x1, · · · , xN+1  such that every pair of them is distinguished by L.

Problem 7. Fix Σ = {a, b}. Pick one of the following, and show it is not regular (using the techniques from lectures).

1. {aibj  : i > j}.

2. {an bm  : n divides m, or m divides n}.

3. {an2  : n ≥ 0}.

4. All strings aibj  such that (a) iis even, or (b) j < i and j is even. (hard)

Extra Practice

Problem 8. Here is an NFA over Σ = {a, b}.  What language does it describe? Transform the NFA into an equivalent DFA, using the method shown in lectures.

Problem 9. Convert the DFA to a regular expression.

Problem 10. Convert the DFA to a regular expression.

Problem 11. Construct a DFA which accepts strings of 0’s and 1’s, where the number of 1’s modulo 3 equals the number of 0’s modulo 3.

Give the corresponding regexp

Problem 12. Construct a DFA which accepts strings of 0’s and 1’s, where the number of 1’s modulo 3 does not equal the number of 0’s modulo 3.

Give the corresponding regexp.

Problem 13.

1. Construct a DFA which accepts binary numbers that are multiples of 3, scanning the most significant bit (i.e.  leftmost) first.  Hint:  consider the value of the remainder so far, as we scan across the number.

2. Construct an automaton which accepts binary numbers which are NOT multiples of 3.

Problem 14.

1. Construct a DFA which recognises binary numbers which are multiples of 2.

2. Construct a DFA which recognises binary numbers which are multiples of 3 (previous exercise)

3. Using these two DFA, construct an NFA which accepts binary numbers which are either not a multiple of 2, or not a multiple of 3, or both. (i.e. 2 is accepted, 3 is accepted, but 6 is not accepted)

4. Convert it to a DFA

5. Swap the accept and non-accept states.  What is the language accepted by this new DFA?