.\" CS 181 Spring 1995 Midterm Slides - ASCII version
.\" From greibach@CS.UCLA.EDU Wed May  3 15:48 PDT 1995
.\"
.\" W 5  5/ 3/95 MT

CS 181 -- Spring 1995
LIST OF SLIDES COVERED FOR MIDTERM (\fBAPPROXIMATE\fP)\u*\d

* -- This list MAY contain material not covered and may omit some
material covered. Remember -- these are JUST SLIDES AND ARE NO SUBSTITUTE
FOR THE TEXTBOOK! You are responsible for EVERYTHING covered in class
or section, whether or not it is in the slides or textbook!

** --If there is no slide list, then (almost) the whole section was covered

SECTION 1A\u**\d -- ORIGINS OF AUTOMATA AND FORMAL LANGUAGE THEORY
SECTION 1B -- GRAPHS AND SETS -- REVIEW
SECTION 1C -- LANGUAGES, WORDS AND OPERATIONS

SECTION 2A -- DEFINITIONS AND EXAMPLES
	skip 2A-13
SECTION 2B -- NONDETERMINISTIC FINITE STATE AUTOMATA
SECTION 2C -- RABIN-SCOTT THEOREM, \(*e-MOVES AND ACCESSIBLE STATES
SECTION 2D -- KLEENE-MYHILL THEOREM AND REGULAR EXPRESSIONS

SECTION 3A -- PUMPING LEMMA AND LANGUAGES THAT ARE NOT FINITE STATE
	skip 3A-9

SECTION 3B -- CLOSURE PROPERTIES
3B-1 -- CLOSURE OF BINARY RELATIONS
3B-2 -- CLOSURE OF OPERATIONS
3B-3 -- CLOSURE OF FAMILIES OF LANGUAGES
3B-4 -- COMPLEMENTATION
3B-5 -- COMPLEMENTATION EXAMPLE
3B-6 -- TWO PARITY LANGUAGES
3B-7 -- INTERSECTION OF L(M\d1\u) and L(M\d2\u)
3B-8 -- CROSS-PRODUCT CONSTRUCTION
3B-9 -- MORE PARITY MACHINES
3B-10 -- CROSS-PRODUCT EXAMPLE -- MACHINES A and B
3B-11A -- CROSS-PRODUCT EXAMPLE -- MACHINE for L(A) \(ca L(B)
3B-11B -- CROSS-PRODUCT EXAMPLE -- MACHINE for L(A) \(cu L(B)
3B-12 -- HOMOMORPHISM
3B-13 -- CLOSURE UNDER HOMOMORPHISM
3B-14 -- INVERSE HOMOMORPHISM EXAMPLE
3B-15 -- INVERSE HOMOMORPHISM
3B-16 -- EXAMPLES OF USE OF CLOSURE PROPERTIES TO SHOW THAT LANGUAGES ARE NOT FS
3B-17 -- REVERSAL
3B-18 -- REVERSAL EXAMPLE
3B-19 -- DETERMINISTIC FSA FOR (L(A))\uR\d

SECTION 3C -- DECISION PROPERTIES
3C-1 -- DECISION PROPERTIES
3C-3. -- USING ACCESSIBILITY ALGORITHM -- EMPTINESS
3C-4.  -- USING ACCESSIBILITY ALGORITHM -- FINITENESS
3C-5. -- TESTING FOR CYCLES USING DEPTH FIRST SEARCH(DFS)
3C-6. -- TESTING FOR CYCLES USING DEPTH FIRST SEARCH(DFS)
3C-10.  -- USING CROSS-PRODUCT AND ACCESSIBILITY ALGORITHM -- EQUIVALENCE
3C-11.  -- USING CROSS-PRODUCT AND ACCESSIBILITY ALGORITHM -- INCLUSION
3C-12. -- USING ACCESSIBILITY ALGORITHM -- UNIVERSE PROBLEM

SECTION 4A -- DEFINITIONS AND EXAMPLES OF CONTEXT-FREE GRAMMARS
4A-6 -- CONTEXT FREE GRAMMAR
4A-7 -- DERIVES RELATION
4A-10 -- EXAMPLE 4A-2 -- GRAMMAR FOR L\deq\u - {\(*e}
4A-11 -- EXAMPLE 4A-3 -- GRAMMAR FOR PAL
4A-12 -- EXAMPLE 4A-4 -- GRAMMAR FOR L\duneq\u

SECTION 4B -- DERIVATION TREES AND AMBIGUITY
4B-2 -- DEFINITION OF DERIVATION TREE
4B-4 -- DEFINITION OF DERIVATION TREE ASSOCIATED TO A DERIVATION
4B-5A -- DEFINITION OF ASSOCIATED DERIVATION TREE (continued)
4B-5B -- DEFINITION OF ASSOCIATED DERIVATION TREE (concluded)
4B-6 -- EXAMPLE 4B-2. DERIVATION TREES IN G\dPAL\u
4B-8 -- DEFINITION OF LR DERIVATIONS
4B-9 -- DEFINITION OF RL DERIVATIONS
4B-10 -- LR DERIVATION LEMMA
4B-11 -- RL DERIVATION LEMMA

Computer Science 181
\fB\s12INTRODUCTION TO FORMAL LANGUAGES AND AUTOMATA THEORY\fP\s0
TOPICS COVERED FOR MIDTERM - Spring 1995
YOU ARE RESPONSIBLE FOR EVERYTHING DONE IN CLASS or SECTION,EVEN IF NOT LISTED

\s12INTRODUCTION\s0

INTRODUCTION and COMMENTS

BACKGROUND REVIEW
graphs, trees, sets, equivalence relations

LANGUAGES, WORDS AND OPERATIONS
alphabet, words, languages
syntax vs semantics
Languages and operations
Kleene operations and Regular expression notation

\s12FINITE STATE AUTOMATA\s0

DEFINITIONS AND EXAMPLES
deterministic finite state acceptor (DFSA)
formal
and informal notation, transition diagrams and tables, L(M)
IDs, yield, yield*, yield+

NONDETERMINISTIC FINITE STATE AUTOMATA
example: nondeterministic diagram for shift register language
example: multiple initial states
notation -- formal and informal, IDs, yield, L(M)

RABIN-SCOTT THEOREM, \(*e-MOVES and ACCESSIBLE STATES
Rabin-Scott algorithm: nfsa \(-> dfsa; 2 forms
accessible, live and dead states: BFS tests for accessibility, liveness
\(*e-moves and their elimination

KLEENE-MYHILL THEOREM and REGULAR EXPRESSIONS
regular expression \(-> ndfsa with \(*e-moves
ndfsa \(-> regular expression

\s12PROPERTIES OF REGULAR (FINITE STATE) LANGUAGES\s0

PUMPING LEMMA and LANGUAGES THAT ARE NOT FINITE STATE
Pigeonhole Principle
L\deq\u = {a\un\db\un\d \(br n \(>= 0 } is not fs
Pumping Lemma
Use of Pumping Lemma to prove languages not fs
	Examples: PAL, L\d<\u, PRIMES

CLOSURE PROPERTIES
Kleene Operations
Complementation
Cross-Product Construction and Boolean operations
Nondeterministic closure properties
	homomorphism, inverse homomorphism, reversal
Use of closure properties to prove not fs

DECISION PROPERTIES
emptiness by BFS (breadth-first search)
finiteness by DFS (depth-first search)
Equivalence, Inclusion, Universe

\s12CONTEXT-FREE GRAMMARS AND LANGUAGES\s0

DEFINITIONS AND EXAMPLES OF CONTEXT-FREE GRAMMARS
Definitions -- \(->, \(:>,\c
.AR *
L(G)
Examples -- EQ, PAL,NOTPAL etc

DERIVATION TREES
Canonical derivations: Left-to-right, right-to-left
Derivation trees