31-10-2012, 05:03 PM
Nondeterministic Finite Automata (NFAs)
NFA.ppt (Size: 106 KB / Downloads: 24)
Expressiveness of DFA
Contains concepts of imperative languages: sequences, branching and loops.
Can implement a newspaper vendor machine (see Page 20 of the book) or even control a character in a video game
Can implement pattern matching: find all text containing “Britney Spears”
Can only implement programs that require a constant amount of memory
NFA vs DFA
Every DFA can be seen as an NFA
But not every NFA can be seen as a DFA
Are DFA’s more expressive? What does this means?
It means that there an NFA can be constructed that accepts a language L for which no DFA can be constructed that accepts L
For example, is there an DFA that accepts the same language accepted by the following NFA?