# Automata Homework

- 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.
- Define a CFG for the language described in problem 1.
- As mentioned in the lecture, it is impossible to recognize the
language A
^{n}B^{n} with a finite state machine.
Is it possible to recognize the language A^{n}B^{n}
where n < 1000 with a finite state machine? Why or why not?
Explain how it could be done or why it could not.
- 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.