AUTOMATA Flashcards
What is a finite automata?
a machine that develops languages and processes symbols from an alphabet into strings
What is the most common form of DFA?
Deterministic finite automata
What are the states of an automata?
Q values (each checkpoint of an automata)W
What is the start state?
The first state, usually identified by an arrow pointing into from nothing.
What is the final/accepting state?
The end states for automaton, usually identified by 2 circles around state.
What is the transition function?
Takes in input state and input symbol to produce an output.
e.g. δ: Q X Σ > Q
also done mathmatically through
δ(Q3,b) = Q3 or δ(Q0,a) = Q1
What are the rules for DFA?
- ONE start state
- ONE OR MORE accepting states
- at MOST one outgoing transition from each state FOR EACH SYMBOL
- NO REQUIREMENT that accepting states are reachable
How is language derived from automata?
Assume M is a finite automata, L(M) is all strings u over Σ satisfying the transition q0 (u)–> q
where q0 is start state and q is accepting state
e.g. ig u is string, u = a,a2,a3,a4,a5..an
and q0 > q1 > q2 > … > qn
STATES CAN REPEAT
How to move on from states?
Must continue unless accepting state if exists another symbol to go down,
What is a non-deterministic automata (NFA)?
Allows same state and symbol to transition to more than one output
What is the transition function for non-deterministic automata?
Δ: Q X Σ > P(Q)
range of transition function is a subset of Q so is powerset of Q ( set of sets of Q)
e.g. if q0 can go multiple directions from symbol b, then mathematically it transitions Δ(q0,b) = {q1,q2} ( A SET!)
What is the empty tranition?
Denoted as NFA^ε
Allows transitions to move to new state without consuming symbol
Called ε steps (epsilon stems)
What is the transition function for NFA^ε?
Δ: Q X (Σ ∪ {ε}) > P(Q)
Shows that symbol step could be empty string ε
ε makes no increase as it is a unit for concatenation
What does a,b or a,ε mean for symbol transitions?
It can be either value for each step
e.g. if a,b
then the transition could be Δ(q1,b) = q2
or Δ(q1,a) = q2
