CS计算机代考程序代写 algorithm Slide 1

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