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.

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