read more

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

Pumping is on the exam.

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

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

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

Practice exams 2.

  • Not hard.
  • WaWR | W in ab*
  • Minimizing finite automata.
  • a) because n and m don’t have to be the same. If it were same, it would not be regular.
  • a) mainly because push-down. Note: Complement of context free language is not necessarily context free.
  • 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).
  • Is grammar ambiguous. It’s ambiguous if the same thing has different derivations (left most or right most).
  • 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.
  • a) true. b) false. c) true. d) false. e) true. f) true. g) true.

Other exam 2

  • Grammar is a little different
  • Same as other test. WcWR. part a) no, yes, no, yes, no, no. b) mentioned before to be WcWR.
  • 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.
  • c, you can do it with a pushdown automata
  • c)
  • 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.
  • Yes?
  • 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.
  • 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