Some Tips about automata

1. Context –sensitive grammar can be recognized by push down automata.
2. CSG can be recognized by 2 –way linear bounded automata.
3. The NDFA is equivalent to DFA.
4. NPDA is equivalent to DPDA.
5. Multi tape turning machine are equivalent to single tape-turning machine.
6. i) Regular grammar – Deterministic finite automata

ii) Context free grammar – Pushdown automata

iii) Unrestricted grammar – Turing machine

iv) Content sensitive grammar – Linear bounded automata 

7.  The power of NPDA & DPDA different.
8. Assume statement s1 and s2 defined as:

s1: L2 –L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively.

s2: The set of all Turing machine is countable.

9.   Given a context free grammar G, there exist an algorithm for determining whether L(G) is infinite.
10. Context sensitive languages are closed under intersection, concatenation, substitution, and inverse homomorphism.
11. Pumping Lemma for context free language states:

Let L be an infinite context free language. Then there exist some positive integers m such that any w belongs to L with |m|>=m can be decomposed as w=uvxyZ with |vxy|<=m and |vy|>=1 such that uv^zxy^z, Z belongs to L for all z=0,1,2,…..

12. a) Every context sensitive language L is recursive.

b) There exist a recursive language that is not context sensitive.

13. Left most derivations does a top down parser use while parsing an input string. The input is scanned from left to right.
14. Given two statements-

S1: If L is regular language then the language {uv | u belongs to L ,v belongs to L^R } is also regular.

S2: L={ww^R} is regular language.

Here S1 is correct and S2 is not correct.

15. a) SLR uses follow information to guide reduction. In case of LR & LALR parser, the look – ahead are associated with the item & they make use of the left context available to the parser.

b) LR grammar is a larger sub – class of context free grammar as compared to the SLR and LALR grammar.

16.