Nondeterministic automata and determinization
The nondeterministic automaton: several possible transitions, ε-transitions and ε-closure, acceptance by path, set of active states and the subset construction that makes it deterministic.
- 24 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Nondeterministic automaton: what is it?
Show the answer
An automaton where a state may have zero, one or several transitions for the same letter, and several initial states.
It has no more power than a deterministic one: both recognize exactly the regular languages. It is often much smaller to write.
When does a nondeterministic automaton accept a word?
- If at least one path labelled by the word leads to an accepting state
- If all paths labelled by the word lead to an accepting state
- If an accepting state is visited at some point during reading
- If the first path tried leads to an accepting state
Show the answer
If at least one path labelled by the word leads to an accepting state
"There exists", not "for all". Going through an accepting state during reading is not enough; the path must end there. And there is no order of trial: all paths count.
In the subset construction, the initial state is the set of … states, and a set is accepting if it contains at least one … state.
Show the answer
In the subset construction, the initial state is the set of initial states, and a set is accepting if it contains at least one accepting state.
A set of active states represents all possible paths at once: one accepting path is enough for the word to be accepted.
ε-transition: what is it?
Show the answer
A transition labelled ε, which may be taken without reading any letter.
It is convenient for assembling automata (union, star) as in Thompson's construction, but can always be removed without changing the language.