Example of -NFA -Closure of a Set of States [Informal definition: If is the set of states from where we can go to other states using then the -closure of is the set of all states that can be reached from elements of by using zero, one or more -transitions.] Let N = (Q, , q0, F, δ) be an -NFA, and let S be any subset of Q. The -closure of S is the set (S) defined as follows: Every element of S is an element of (S); For any q  (S), every element of δ(q, ) is in (S); No elements of Q are in (S). The Extended Transition Function for an -NFA Let N = (Q, , q0, F, δ) be an -NFA. We define the function : Q  → 2Q as follows: 1. For any q  Q, (q, ) = ({q}) Acceptance of a string or language by an -NFA Let N = (Q, , q0, F, δ) be an -NFA. A string x  * is accepted by N if (q0, x) F ≠ (i.e., (q0, x) contains at least one accepting state). The language accepted / recognized by N, is the set L(N) = { x  * | (q0, x) F ≠ } 3.5 Kleene’s Theorem Part 1: Any regular language can be accepted by a finite automaton. Part 2: The language accepted by any finite automaton is regular. Theorem 4.3 (of Martin) [It’s just Kleene’s theorem expressed in another way] For any alphabet , and any language L *, three statements are equivalent if L is regular: L is recognized by an FA / DFA. L is recognized by an NFA. L is recognized by an -NFA. 3.6 Algebraic Laws for Regular Expressions
Step 3: Now, as the string is like x0y, therefore, we must start from the NFA of step 1 and finish at the NFA at step 2. However, we have to insert a 0-transition from the DFA of step 1 to the DFA of step 2. Now, if |x| = 0, then |y| must be 5. So, we can insert a 0-transition from state A to G. Step 4: Similarly, if |x| = 1, then |y| must be 4. So, we can insert a 0-transition from state B to H. And in similar manner, we get: Simplify the RE as much as possible: a*b + a*bbb* + a* and draw the equivalent FA. a*b + a*bbb* + a* = a*(b + bbb* + ) = a*(b ( + bb*) + ) = a*(bb* + ) [ + xx* = x*] = a*b* [ + x* = x*] Equivalent -NFA: Equivalent NFA: Equivalent DFA: Find a string that is represented by both the regular expressions r and s and is not represented by either r or s where r = a* + b* and s = ab* + ba* + b*a + (a*b)* a aba Write down an RE that represents all strings w over {0, 1} such that the first and last characters of w are the same and w contains at least three 0’s. Step 1: The string contains at least three 0’s. 000
(a + b)( + aa)+ + (a + b) = (a + b) (( + aa)+ + ) = (a + b)( + aa)* [x+ + = x*] = (a + b)(*(aa)*)* [(x + y)* = (x*y*)* = (x* + y*)*] = (a + b)((aa)*)* = (a + b)(aa)* [(x*)* = x*] Find an FA that accepts all strings over {a, b} that or end with aa or bb. Step 1: RE that accepts all strings that begin with aa or bb: (aa + bb)(a + b)* Step 2: RE that accepts all strings that end with aa or bb: (a + b)*(aa + bb) Step 3: RE that accepts all strings that begin or end with aa or bb: (aa + bb)(a + b)* + (a + b)*(aa + bb) Step 4: NFA for (aa + bb)(a + b)*: Step 5: NFA for (a + b)*(aa + bb): Step 6: -NFA for (aa + bb)(a + b)* + (a + b)*(aa + bb): Equivalent NFA: Draw the transition diagram of the DFA accepting the languages over {0, 1} The set of all strings that has at least two 0’s. The set of all strings that does not end in 0010. Step 1: DFA that accepts strings that end with 0010: Step 2: DFA that accepts strings that does not end with 0010:
Write down a regular expression for the language L = {w {a, b}* | w does not contain an occurrence of ab}. Step 1: w should not contain ab. So, the RE for w cannot be a*b, ab* or a*b*. However, the RE for w may be , a*, b*, or b*a*. Note that the RE b*a* includes the REs , a* and b*. Step 2: Therefore, the final RE is b*a*. Find and draw the minimum-state DFA for the DFA below: Transition Table of the given DFA: State a b → 1 2 3 2 4 5 3 6 7 * 4 4 5 5 6 7 * 6 4 5 * 7 6 7 Minimization of the given DFA: Step 1: Separating final and non-final states, we get the following groups: {1, 2, 3, 5} {4, 6, 7} Step 2: From the group {4, 6, 7}, we separate the group {4, 6} as they move to the non-final group {1, 2, 3, 5} for the input symbol b. {1, 2, 3, 5} {4, 6} {7} Step 3: From the group {1, 2, 3, 5}, we separate the group {3, 5} as they move to the final group {7} for the input symbol b. {1, 2} {3, 5} {4, 6} {7} Step 4: From the group {1, 2}, we separate the elements into two groups as for the symbol a, state 1 remains in the same group whereas state 2 moves to the group {4, 6}. {1} {2} {3, 5} {4, 6} {7} Diagram of the minimum-state DFA: Find the regular expression equivalent to the DFA in the following figure: States Inputs 0 1 →* Q1 Q1 Q2 Q2 Q3 Q2