Automata Homework

  1. Define a finite state machine that accepts the languages that contains the two strings "ABCBCBA" and "ABCCCBA" given the input symbols {A,B,C}. In other words, recognize the language ABC(B|C)CBA.
  2. Define a CFG for the language described in problem 1.
  3. As mentioned in the lecture, it is impossible to recognize the language AnBn with a finite state machine. Is it possible to recognize the language AnBn where n < 1000 with a finite state machine? Why or why not? Explain how it could be done or why it could not.
  4. Can you make a finite state machine that accepts only strings that are palindromes? Can you make a CFG that accepts only strings that are palindromes?

Navigate this Web site.

Contact.