TOC 1.2 (pp. 47-54) NFA
- Due Sep 22, 2021 by 11:59pm
- Points 15
- Submitting a file upload
- File Types pdf
Goals
- Intro to NFA
Tasks
Pick any 5 below, but must have at least 1 NFA.
1. Compare these features between an DFA and NFA (p48):
- Transitions per symbol
- Concurrency
- ε Transitions
2. Why is a DFA also an NFA? (p47)
3. Why isn't an NFA also a DFA? Careful -- whether an NFA can be reduced to a DFA is a different question. (p53 vs p35)
4. Are NFA's more powerful than DFA's? (p54)
5. For the DFA on p52, imagine removing the start transition, start state, and ε's (but not the transition arrows). What are you left with? What does this suggest is a common use case for ε transitions?
NFA Practice (can upload an images along with text answers if needed)
6. Draw an NFA that accepts strings where the third to last symbol is "0" using 4 states (e.g. 1011)
7. Draw an NFA that accepts strings with either an even number of 0s or exactly two 1s in 6 states.
8. Draw an NFA that accepts the language A*B*A*A in 3 states. Recall that * means 0 or more.
Submission
Please turn in the assignment in Canvas.