Week 1 - GNFA Flashcards
What is a Generalised Nondeterministic Finite State Automata (GNFA)?
A NFA where transition arrows may have regular expressions as labels, that can read blocks of symbols from the input rather than a single symbol.
What restrictions are imposed on GNFA in our course?
The initial state has no arrows coming into it.
The initial state has arrows to all other states except itself.
There is only one final state.
There are arrows from all states to the final state.
There is no arrow that transitions to the final state.
Except for the initial and final states, each state has an arrow to any other state including itself.
Define a GNFA in terms of compution.
A finite automaton is a 5-tuple (Q, Σ, δ, qStart, qAccept), where
Q is a finite set of states.
Σ is a finite set called alphabet.
qStart is the initial state.
qAccept is the final state.
δ is a function (Q \ {qAccept} x Q \ {qStart} -> R), the transition function.
Where R is the set of regular expressions ever Σ.
How do you convert a DFA to a GNFA that accepts the same language? Assume that M is the DFA, the Language is A and the GNFA is G.
Add a new qStart and qAccept state to M. The qAccept is now the only final state, and qStart is the new initial state.
Add a Ɛ transition from qStart to the old initial state of M.
Add Ɛ transitions from the old final states of M to qAccept.
For arrows in M that have multiple labels or if there are multiple arrows between two states, replace them with one arrow labelled with the union of the labels.
Add Ø transition between states that do not have arrows between each other, including self arrows.
You now have a GNFA.
How do you delete states from a GNFA?
You take a state qRip. You need to compensate for qRip being missing by adding transitions between any state that can transition to qRip that can reach any states that qRip transitions to. The labels of these new transitions will be as follows.
Assuming that the transition between a state qI in qRip is labelled R1, and the transition between qRip and a state qJ is labelled R2, the loop transition from qRip going to itself is R3, and the transition between state qI and qJ is R4. Then the new regular expression is (R1R2(R3*))∪R4.
How do you convert a GNFA to a regular expression?
You delete states in the GNFA until it becomes only two states: qStart and qAccept that have only one transition going between them (from qStart to qAccept). The label of this transition is the regular expression.
This regular expression characterises the language accepted by the GNFA.
TRUE OR FALSE: A language is regular if and only if a regular expression describes it.
TRUE.
