- Question 4 Finite Automata And Decision Algorithms A Consider The Following Fa M That Accepts Some Language C 115 2 X 1 (157.35 KiB) Viewed 57 times
Question 4 Finite Automata and Decision Algorithms a. Consider the following FA M that accepts some language C: 115% 2 X 3 X 4 X XX 5 X XX X 6 X X X q 1 2 3 4 5 - In the process of finding the minimum-state FA Mmin that accepts L, we obtain the following diagram after completion of the final pass of the algorithm for marking the pairs of states (p, q) with p q. Here X indicates that a pair is marked and an empty block indicates that a pair is not marked. On the following page, give Mmin as a diagram. In each state of Mmin, indicate clearly which states of M it represents. 8 mark(s) ✔ Q b. Let n ≥ 1. Let n be even; in other words, n = 2m for some m 2 1. Let L= { {a,b}" | |x| = n and no (x) = n(x)}. Consider a Finite Automaton M which has (i) The transitions of M are: 125% • a state for each of the ordered pairs (i, j), where 0 ≤ i ≤ m and 0 ≤ i ≤m, and i and j represent the numbers of a's and b's, respectively, in the input string, • and a state N for all the nonprefixes of elements of L. Complete the following: 1. If i <m, then 6 ((i, j), a) = 2. Ifj<m, then 8 ((i, j), b) = 3. If jm, then 8 ((m, j), a) =. 4. Ifim, then 8 ((i, m), b) = (ii) The number of states in M can be expressed in terms of m. It is C 6 mark(s)