1: Regular languages and FSAs Flashcards
What is a FSA?
Finite state automaton = a model of a simple computer that moves between one of each of a finite set of states according to external inputs.
What is an alphabet?
A finite set of symbols, called letters.
What is a letter?
One item (symbol) within an alphabet.
What is a word? What is the empty word?
A finite sequence of letters over (within) an alphabet. Word aka string. The empty word has a length of 0 so has no letters.
If A is an alphabet, what is A*?
A* = the set of all words over (that can be built from) the alphabet A, including the empty word. Words are built from 0 or more letters from the alphabet. Languages from the alphabet A will be subsets of A*.
What is a DFA?
A deterministic finite state automaton is a variant of a FSA. It is the “default” and cannot be (modelled as being) in more than 1 state simultaneously, as a nondeterministic finite state automaton is able to be.
How do you define a DFA?
You define DFAs as tuples of 5 items as M = (A, S, F, s0, T).
A = alphabet S = set of states F = transition function, which takes a non-empty input letter and current state and returns (and goes to) another state s0 = start state; s0 ∈ S T = set of accept states, aka terminals. T is a subset of all states: T ⊆ S.
What is a terminal also known as?
A terminal is aka an accept state.
What is a transition function?
Transition functions are used to translate between current states to the next ones according to inputs in FSAs.
What is a regular language?
Languages are regular when there is a DFA whose language is the same as the language in question.
What is an NFA?
A nondeterministic finite state automaton (NFA) is a variant of a FSA which can be modelled as being in more than one state simultaneously. Thinking of the current states of machines as brances of a tree, only one leaf node needs to accept at some point for the NFA to accept the input.
How do you define an NFA?
You define NFAs as a tuple of 5 items such that M = (A,
S, F, s0, T).
A = alphabet S = set of states F = transition function, which takes an input letter (which can now also be empty) and current state and returns (and goes to) another state in the power set of S, P(S), which is the set of all subsets of S (since some may become cut off) s0 = start state; s0 ∈ S T = set of accept states, aka terminals. T is a subset of all states: T ⊆ S.
What is the language defined by an NFA?
The language will consist of all the words that the NFA accepts.
Prove that if a language is accepted by an NFA if and only if it is accepted by a DFA.
Let N = (A, S, F, s0, T) be an NFA. We construct a DFA M that accepts L(N). We let M = (A,P(S), F’, S0, T’), where:
• The transition function F’ : A x P(S) → P(S) is given by:
F’(a, X) = {y ∈ S : ∃ x ∈ X with a path labelled ϵ ^ i a ϵ ^ j = a from x to y in N, for some i, j ≥ 0}.
- The start state is S0 = {s0} ∪ {s : there exists a path labelled only with ϵs from s0 to s}.
- The new set of accept states is T’ = {Y ⊆ S : Y ∩ T ≠ ∅}, which is all sets of states containing at least one accept state of N.
To finish the proof, we need to show that L(M) = L(N). To do this, we first show that L(N) ⊆ L(M) and then that L(M) ⊆ L(N). To see that L(N) ⊆ L(M), let w = a1 a2 … an ∈ L(N). Then there is a path in N: S0 → a1 S1→ a2 S2 → ··· → an Sn ∈ T’.
Let S1 = F’(a1, S0), S2 = F’(a2, S1), …, Sn = F’(an, Sn-1). Then s1 ∈ S1, s2 ∈ S2, …, sn ∈ Sn ∈ T’. So there is a path in M: S0 → a1 S1 → a2 S2 → ··· → an Sn ∈ T’. So w ∈ L(M). Therefore L(N) ⊆ L(M).
We finish the proof by showing that L(M) ⊆ L(N). Let w = a1 a2 … an ∈ L(M). Then there is a path in N:
S0 → a1 S1 → a2 S2 → ··· → an Sn ∈ T’.
By definition of T’, there exists some sn ∈ Sn ∩ T. Hence there exists some sn-1 ∈ Sn-1 such that sn-1 → an Sn is a transition in N.
Continuing in this fashion, we eventually conclude that s0 ∈ S0 = {s0} and there exists a transition s0 → a1 s1 in
N.
Therefore we can conclude that in N there is the path:
s0 → a1 si1 → ··· → an sin ∈ T and so w ∈ L(N).
How do you convert an NFA into a DFA?
To make a DFA M from an NFA N = (A, S, F, s0, T). The alphabet of M is A.
- Begin with a new start state S0 labelled by {s0} ∪ {s : there exists a path labelled only by ϵ-arrows from s0 to s}.
- For each newly constructed state Si, and for each a ∈ A:
(a) For each s ∈ Si, find all states s’ that can be reached from s by reading (ϵ ^ i)a(ϵ ^ j) (for any i and j).
(b) Let Sj be the set of all of these states s’. (The set Sj may be the empty
set ∅) Put an arrow labelled a from Si to Sj . - Repeat Step 2 until every new state Si has one arrow leaving it for each letter a ∈ A.
- Make each state Si that contains at least one state from T into an accept state for M.
