CH2 - Regular Languages and Finite State Automata Flashcards
Define a DFA.
Do you recall how to draw a transition diagram of M?
What does each word describe on the graph?
We generally draw the vertices as circles rather than dots, and write the name of the state
inside the circle. We label the start state with a half-arrow pointing into it (coming from
nowhere), and label the accept states with double rings.
In any transition diagram, each vertex (each state) has one and only one arrow going out of it for each letter in the alphabet, so each word describes a unique directed
walk from q_0.
When does the DFA accept the word w?
Define the extended transition function.
Define the language defined by M.
When is a language regular? How can we show it is regular?
When the unique directed walk
from q_0 ends in a state from T.
To show that a language is regular, we construct a DFA accepting it.
Define a sink state.
Define an NFA.
Sink state: once we reach it we can never leave it.
Accepting a word and languages defined by N have similar definitions to DFAs.
Notice that some of the yis may be equal to the empty word, so that the walk may have length greater
than |w|.
We think of an NFA as computing in parallel, so more than one branch of computation may be “alive” at the same time. It accepts if any of the branches of computation accepts.
Define the extended transition function of an NFA.
State THM 2.2.5 on DFA’s vs NFA’s.
Give the procedure for constructing a DFA from an NFA.
Define a regular expression.
State the languages corresponding to different regular expressions.
State the theorem on closure under union, star …
State Kleene’s Theorem.
What is Kleene’s method to convert from a regular expression to an NFA?
What is Kleene’s method to convert from an NFA to a regular expression?
State the Pumping Lemma.
How can you use the Pumping Lemma to prove that a language is not regular?
