read more 
When are context free languages closed? Under blah and blah etc. 


Pumping is on the exam. 




1. Minimizing finite automata: all the relations, the approximate relations. 
equivalence classes. 
equivalent with respect to automata, then they’re equivalent with respect to language of automaton. 

2. Algorithms for regular languages: 
Could be useful for the exam. 2.6 or 2.7. Could be on the exam but won’t be heavy. 

3. Context free grammars. Parse trees. Push down automata. Push down automata and context free languages. 


Practice exams 2. 

1. Not hard. 

2. WaW^R | W in ab*

3.  Minimizing finite automata. 

4. a) because n and m don’t have to be the same. If it were same, it would not be regular. 

5. a) mainly because push-down. Note: Complement of context free language is not necessarily context free. 

6) If you can add something to the two sides and get them not equal (that is, one in L and one in the string), then they’re not equivalent. If no matter what you add you get them both in L or both outside of L, then they’re equal (statement is true). 

7) Is grammar ambiguous. It’s ambiguous if the same thing has different derivations (left most or right most).

8) You have to have a strategy no matter what A does. You should have “A picks the integer n”, rather than picks a specific number. That makes NC State proof better because it’s more general. 

9) a) true. b) false. c) true. d) false. e) true. f) true. g) true. 

Other exam 2 

1) Grammar is a little different 

2) Same as other test. WcW^R. part a) no, yes, no, yes, no, no. b) mentioned before to be WcW^R.

3) Look at handout for minimizing automata. Could do color . Figure out what language it recognizes and then figure out a simpler way to write it and then that’ll be minimal. Usually it’ll be like odd number of char or even or something. 

4) c, you can do it with a pushdown automata 

5) c) 

6) a is true (because you can add anything and they’ll both be in or won’t be in language) b is false. c is true? because nothing you put on the end will put them in the language. d true for same reason. 

7) Yes? 

8) We’re saying that A can always win which means the language is regular? You cannot show a language is regular by showing that the opponent wins. No way by using the game can you show a language is regular. 

9) a) false b) true c) true d) false 

extra credit a) t b) false c ) false d) true e) true f) true (think about push down and finite automata being merged) g) true