**Closure under operations(4.1):**

Union

Intersection

*Draw the FSA for L1 ∩ L2 where L1 = {ba ^{n}b^{m}a^{k}: n,m>=0,k>=1} and L2 = {b^{m}a^{k}, 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.*

**Elementary Questions about Regular Languages(4.2):**

Easy questions to answer:

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 languag*e 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.*

**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: a ^{n}b^{n}c^{k}:
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 | λ*

**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: a^{n}b^{n},
na = nb, ww^{R}

* 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?*...

**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