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 ) is in (S);  δ(q, 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. Martin) [It’s Theorem 4.3 (of just Kleene’s theorem expressed in another way] For any alphabet and any language three statements are equivalent , L *, if L is regular: L is recognized by an FA / DFA. is recognized by an NFA. L L is recognized by an -NFA. 3.6 Algebraic Laws for Regular Expressions
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
Automata_Study_Guide.docx