## Review for Exam 2

### Chapter 4: Properties of Regular Languages:

Closure under operations(4.1):
Union
Intersection
Draw the FSA for L1 L2 where L1 = {banbmak: n,m>=0,k>=1} and L2 = {bmak, m,k >=1}
Concatenation
Negation
Star-closure
Complementation
Difference
Reversal
Homomorphisms
Right Quotients

Prove that the family of regular languages is closed under a new operation
Prove that the family of regular languages is closed under cor, where
cor(L1,L2) = {w | w is not an element of L1, or w is not an element of L2}

Prove that a new language is regular.
Prove that the language L = {uv: u is in L1, and |v| is 2} is regular if L1 is regular.

Membership: Is this string in the language? Run the string through the automata
Finite or Infinite Language: Look for loops in the automata
Empty Language: No reachable final state
Equality: Test if L1 = L2 by testing if (L1 ∩ L2) U (L1 L2) is empty

Show that there is an algorithm for doing some operation:
Give an algorithm for determining if L1 is a subset of L2.

Identifying Non-Regular Languages (4.3):

Pumping lemma: an infinite regular language must have a cycle in the DFA, which can be travelled infinitely or not at all. Proofs using the pumping lemma are proofs by contradiction.

Prove that a language is not regular.
Prove that the language L = {w: na(w) > nb(w)} is not regular.

### Chapter 5: Context-Free Languages

Context-Free Grammars (5.1)
CFG Definition
Leftmost and Rightmost Derivations
Derivation Trees and Sentences
Give a LeftMost derivation and parse tree for the string abbbb in the language defined by the following grammar:
S -> aAB
A -> bBb
B -> A | λ

Write a CFG for the following language: anbnck: n >0 and k>= 3}

Parsing and Ambiguity (5.2)
Parsing - not as easy as for regular languages
Exhaustive Search Parsing
Tweaked ESP so that it terminates
Best running time for parsing CFG?
Simple Grammar Definition
Best running time for parsing Simple Grammars?
Ambiguous Languages
Show that this grammar is ambiguous:
S -> aSb | SS | λ

### Chapter 6: Grammar Simplifications and Normal Forms

Simplifying Grammars (6.1)
Useless Productions:
Unreachable (Dependency graph)
Doesn't Terminate (V set)
Removing Lambda-Productions
Removing Unit Productions
Order: Lambda, Unit, Remove Useless
Completely simplify a grammar:
S-> aA | aBB
A -> aaA | λ
B -> bB | bbC
C -> B

Two Important Normal Forms (6.2)
Chomsky Normal Form
Convert the grammar into Chomsky Normal Form:
S -> ABa
A -> aab
B -> Ac

Greibach Normal Form
Convert the grammar into Greibach:
S -> AB | abSb | aa
A -> aA | bB | b
B -> b

### Chapter 7: Pushdown Automata

Nondeterministic PDA (7.1)
Mathematical Definition
Language is accepted if any transitions lead to final state
Three main types of stack uses: anbn, na = nb, wwR

Write a PDA for the language L= {w: na(w) > nb(w) + 3}

PDAs describe Context-Free Languages (7.2)
Convert any CFG into a PDA:
First convert to Greibach, then write PDA rules
Write a PDA for the language described by:
S -> aSbb | aab

Deterministic PDAs (7.3)
Deterministic PDA's are not as powerful as Nondeterministic PDA
Defines new family: Deterministic CF Languages
DPDA can have lambda, must not have a choice of transition based on String and stack
Is this PDA deterministic?...

### Chapter 8: Properties of Context-Free Languages

Closure Properties and Decision Algorithms (8.2)
CFLS are closed under: Star operator, concatenation, union, regular intersection
CFLS are NOT closed under: intersection and complementation
Decidable properties include whether or not a Language is empty (Start symbol is useless) and whether or not a language is infinite (Dependency graph contains loops)

These properties can be used to show a language is Context-free or not Context-free

Prove that the language: L = {w : na(w) > nb(w) and w does not contain the substring aba} is context-free.

Know the definitions of each type of grammar:
Simple, Context-Free, Regular, Chomsky Normal Form, Greibach Normal Form