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 AⁿBⁿ with a finite state machine. Is it possible to recognize the language AⁿBⁿ 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?