COMP 335

IMPORTANT TIPS:

  • If you have Prf. Shiri (as I did) be aware that at least a few exam questions will be taken directly or be very similar to questions from the assignments
  • If you are writing too much, you are probably wrong. Many answers are one line or just a few words
  • For questions that ask you to prove something about languages ALWAYS consider the following three languages and you will probably find a counterexample to what is being requested for proof:
    1. ∅
    2. {λ}
    3. Σ*

NOTES:

L1 & L2 are context free then:

  • L1 ∪ L2 is context free
  • L1L2 is context free
  • L1* is context free
  • L1 ∩ L2 is not necessarily context free
  • ¬ L1 is not necessarily context free

Converting Right Linear grammar to Left Linear Grammar

  1. Draw FA from RL grammar
  2. Reverse it
  3. Get RL grammar of reverse
  4. Reverse the RHS of grammar to become LL grammar

Converting Left Linear grammar to Right Linear Grammar

  1. Reverse it to RL
  2. Draw FA
  3. Reverse FA
  4. Get RL grammar from the FA

Converting to Chomsky Normal Form steps:

  1. Get rid of all null productions
  2. Get rid of all productions where RHS is one variable
  3. Replace every production that is too long (i.e. X -> ABC) with shorter productions
  4. Move all terminals to productions where RHS in one terminal

RESOURCES:

Very clear course slides from U of San Francisco

Great slide about NFA to DFA Algorithm and the Transition table process HERE

Course page at Rensselear with many homeworks and solutions

Context Free Grammar Pumping Lemmas slides

Chomsky Normal Form conversion – clear steps from UC Davis

EXAMPLES:

Assignments and Solutions from previous COMP 335 with Prof. Shiri

Assignments and Solutions from previous COMP 335 with Prof. Grahne

From Cornell:

Example Questions on Regular and Non-Regular languages, from Harvard

Sample Midterm with great examples, from Standford

Midterm with Solutions from Worcester Polytechnic

One comment on “COMP 335”

Leave a comment