Slide 1
Midterm Review
Regular Languages
Finite State Machines (FSM)
Deterministic (DFSM)
Nondeterministic (NDFSM)
Regular Expressions
Regular Grammars
Moore and Mealy Machines
Conversions
DFSM
NDFSM
Reg. Expressions
Reg. grammars
Minimal DFSM
subset constr.
Thompson
rip
Regular language
L
Conversions
NDFSM -> DFSM
DFSM -> minimal DFSM
Reg.Exp. -> NDFSM
NDFSM -> Reg.Exp.
IS Regular
Prove that a language is regular
Construct a:
DFSM
NDFSM
Reg.Exp.
Reg.Grammar
Prove that L has finitely many classes
Build minimal DFSM
Closure Properties
Union
Concatenation
Kleene star
Complement
Intersection
Difference
Reverse
IS NOT Regular
Prove that a language is not regular
Use pumping theorem
Use closure operations
Decision Problems
Membership
Emptiness
Totality
Finiteness
Equivalence
Minimality
Specific questions
Pattern Matching / Searching
Pattern p and text T:
Matching: L(*p *)
Searching: L(*p)
Context-Free Languages
Context-Free Grammars (CFG)
Pushdown Automata (PDA)
Conversions
CFG -> Chomsky Normal Form
Algorithm
CFG -> unambiguous CFG
No algorithm
IS Context-Free
Prove that a language is context-free
Construct a:
CFG
PDA
Closure Properties
Union
Concatenation
Kleene star
Reverse
Intersection with regular language
Difference with regular language
Complement – NOT
Intersection – NOT
Difference – NOT
IS NOT Context-Free
Prove that a language is not context-free
Use pumping theorem
Use closure operations
Intersection with a regular language
Decision Problems
Membership
Emptiness
Finiteness
Specific questions