Some tips about Automata

1. A Turing Machine cannot solve halting problem.
2. Set of Recursive Enumerable languages are closed under union.
3. Context Sensitive grammar can be recognized by a linearly bounded memory machine.
4. Recursive Languages are closed under union.
5. If a Language & its complement is both regular, then the language must be recursive.
6. A Language is accepted by Finite Automata if and only if it is recursive.
7. Every recursive language is recursively enumerable.
8. A language is accepted by FA iff it is context free.
9. A language is accepted by FA iff it is right linear.
10. Any regular language has an equivalent CFG.
11. Recursively enumerable languages are closed – a) complementation, b) Union, but not closed under intersection.
12. The regular sets are closed under a) union, b) concatenation, c) kleene’s closure, d) intersection
13. The class of regular sets is closed under homomorphism.
14. Context Sensitive Grammar can be recognized by FSM.
15. The intersection of Context Free Language & Regular Language is always Context free.
16. Any regular language has an equivalent context free grammar.
17. Some non – regular languages can’t be generated by any context free grammar.
18. The intersection of context free language is always context free.
19. The Language constructs which are most useful in describing nested structures such as balanced parenthesis. ----- Context free grammar
20. Context –sensitive is most general phase – structure grammar.