Nondeterministic Finite State Machine NFA Examples and Concepts

Nondeterministic Finite State Machine (NFA) 2ndSemester 2017-2018 Dr. Abdulhussein M. Abdullah Lec #4

Can DFA's be designed to accept any string?

Examples Design a DFA to recognize strings that start out with k zeros followed by k ones. Design a DFA to recognize strings with an equal number of ones and zeros. Design a DFA to recognize strings with an equal number of strings "01" and "10"

Actually the third one is regular! 0 1 1 0 0 1 0 1 0 1 DFA to recognize strings with an equal number of strings "01" and "10"

Nondeterministic Finite State Machine NFA A Nondeterministic Finite Automata is a quintuple M = (K, , , s, F) where K is a finite set of states as an alphabet s K is the initial state F K is the set of final states is the transition function from K x K (p, a) = {q}

A nondeterministic finite automata (NFA) allows transitions on a symbol from one state to possibly more than one other state.

Allows -transitions from one state to another whereby we can move from the first state to the second without inputting the next character.

In an NFA a state may have zero, one, or more exiting arrows for each symbol of the alphabet. = {a, b, c}

Basic NFA Ideas Computation Start in start state If any transitions, clone a machine for each Read a symbol, clone a machine for each matching transition If a symbol is read and there is no way to exit from a state, that machine dies. At end of input if any machine accepts then accept

Example: Read: 010110 0,1 0,1 0, 1 1 1 2 3 4 Accept strings containing either 101 or 11 as a substring

alphabet = {0,1} NFA operation Example of NFA operation: 1 0, 1 0,1 0,1 input: 0 1 0 not accepted

NFA operation alphabet = {0,1} Example of NFA operation: 1 0, 1 0,1 0,1 input: 1 1 0 accepted

Read: 010110 0,1 0,1 0, 1 1 1 2 3 4 1 0 1 1 1 2 3 0 1 3 1 1 2 3 4 1 2 1 3 4 4 0 1 4 4 3

Why? NFAs can express simple automata that would be extremely complex in DFA form Theorems and algorithms exist that show that any DFA can be converted into an NFA and any NFA can be converted to a DFA Theorems also exist showing why union, concatenation and star operations on regular languages produce regular languages.

N = (Q, , , Q0, F) 1 Q = {q1, q2, q3, q4} = {0,1} Q0= {q1, q2} q4 q2 0 , 0 q3 F = {q4} Q 0 0 1 q1 q1 {q3} q2 {q4} 00 L(N)? {q2,q4} {q2} q3 01 L(N)? q4

Example Let A be the language consisting of all strings over {0, 1} containing a 1 in the third position from the end, i.e. A = {x {0, 1}|x = w1v, |v| = 2} Example: 000100 A but 0011 does not belong to A

Equivalence of Machines Definition: Machine is equivalent to machine 1 M ( ) ( 2 1 M L M L = M 2 ) if

Example of equivalent machines M NFA 1 0 ( ) 1= 10 { } * L M 1 q q 0 1 M DFA 1 , 0 2 0 ( ) 2= 10 { } * L M 1 1 q q q 2 0 1 0

Theorem: = Languages accepted by NFAs Regular Languages Languages accepted by DFAs NFAs and DFAs have the same computation power, accept the same set of languages

Proof: we only need to show Languages accepted by NFAs Regular Languages AND Languages accepted by NFAs Regular Languages

Proof-Step 1 Languages accepted by NFAs Regular Languages Every DFA is trivially an NFA Any language is also accepted by an NFA accepted by a DFA L

Proof-Step 2 Languages accepted by NFAs Regular Languages Any NFA can be converted to an equivalent DFA L Any language is also accepted by a DFA accepted by an NFA

Conversion NFA to DFA a M NFA a q 1 q q 0 2 b M DFA 0 q

( q , a ) { q , q } * = 0 1 2 a M NFA a q 1 q q 0 2 b M DFA a 0 q 1,q q 2

empty set ( q , b ) * = 0 a M NFA a q 1 q q 0 2 b M DFA a 0 q 1,q q 2 b trap state

( ( q q , , a a ) ) { q , q } * = = 1 1 2 * 2 a NFA M a union q 1 q q 0 2 1,q q b 2 a M DFA a 0 q 1,q q 2 b

( ( q q , , b b ) ) { { q q } } * = = 1 0 a * M NFA 2 0 a union q 1 q q 0 2 0 q b a b M DFA a 0 q 1,q q 2 b

a M NFA a q 1 q q 0 2 b a b M DFA a 0 q 1,q q 2 b a, b trap state

END OF CONSTRUCTION a M NFA a q 1 q q q 1 F 0 2 b a b M DFA a 0 q 1,q q F 2 1, q q 2 b a, b

General Conversion Procedure M Input: an NFA M (M Output: an equivalent DFA with ( ) = ) L M L

The NFA has states , , ,... q q q 0 1 2 The DFA has states from the power set , , , 1 0 , .... , q q q , q q , q , q 0 1 1 2 3

Conversion Procedure Steps step q 1. Initial state of NFA: 0 * ( ) = q , q , 0 0 q , Initial state of DFA: 0

Example ( ) = q , q * 0 0 a M NFA a q 1 q q 0 2 b M DFA 0 q

step { , ,..., } q q q 2. For every DFA s state i j m compute in the NFA * ( ( ... ) q , a , i ) Union * q a { q , q ,..., q } j = n k l ( ) * q , a m add transition to DFA ( , { i ) q q ,..., q }, a { q , q ,..., q } k n = m j l

= * ( , ) { , } q a q q Example 0 1 2 a M NFA a q 1 q q 0 2 b M DFA a 0 q 1,q q 2 ( q ) = , , a q q 0 1 2

step 3. Repeat Step 2 for every state in DFA and symbols in alphabet until no more states can be added in the DFA

Example a M NFA a q 1 q q 0 2 b a b M DFA a 0 q 1,q q 2 b a, b

step { , ,..., } q q q 4. For any DFA state i j m if some is accepting state in NFA j q Then, { , ,..., } q q q i j m is accepting state in DFA

Example a M NFA q 1 F a q 1 q q 0 2 b a b M DFA a 0 q 1,q q F 2 1, q q 2 b a, b

Properties of Regular Languages

L 1 L For regular languages we will prove that: and 2 L L Union: 1 2 1L L Concatenation: 2 Are regular Languages Star: * 1 L L1 R Reversal: Complement: Intersection: 1 L L L 1 2

We say: Regular languages are closed under L L Union: 1 2 1L L Concatenation: 2 Star: * 1 L L1 R Reversal: Complement: Intersection: 1 L L L 1 2

Take two languages 1 L Regular language L Regular language 2 ( ) ( ) = = L M L L M L 1 1 2 2 M M NFA NFA 1 2 Single accepting state Single accepting state

Example M 1 0 n a n = { } L a b b 1 M 2 a ba b L = 2

Union L L M 1 2 1 NFA for M 2

Example n = { } { } L L a b ba NFA for 1 2 n = { } L a b 1 a b L = { } ba 2 a b