Mumbai university > Comp > SEM 4 > TCS

Marks: 2M

Year: MAy 2014

• When machine is in a given state and reads asymbol, the machine will have a choice ofwhere to move to next.

• There may be states where, after reading a givensymbol, the machine has nowhere to go.

• Applying the transition function will give, not just a single state, but zeroormorestates

Example: (11 + 110)*0

• A string will be accepted if there is at least one sequence of state transitions on an input that leaves the machine in an accepting state.

• Such a machine is called a non-deterministic finite automata (NDFA)