flat imp 2mid

Unit 5

1.what is meant by ambiguous grammar? Check whether the following grammar is ambiguous  or not

s->ss

s->a

2. what is charmskey normalform and greyberg normal form? Construct cnf  for the following grammer s->bA/aB      A->aAA/as/a      b->aBB/bs/b

3.construct grammer in gnf for the following grammer whose production rules are as follows

s->aa/0

a->ss/1

4.explain e productions,unit productions ,useless symbols in the grammar with example find out context free grammar by elemating useless symbols in the following grammar

s->AB/CA

B->BC/AB

A->a

C->aB/b

5.construct grammer in cnf and gnf for the following grammer s->s0/0

UNIT 6

1.What is pda? Explain model of pda? Difference between determenstic pda and non deterministic pda..

2.construct pda for the following the following language l=(wcw^r)/w belongs to (01)*

3. construct pda for the following the following language l={a^nb^n/n>/1}

4.explain the different types of moves in pda? What is instantaneous description ? what is meant by acceptance of final state.and acceptance by empty stage

5.construct pda for the following grammer s->aAA   A->as/bs/a verify the results for the string aabaaa

Unit 7

1.explain different types of turing mechines?

2. explain turing machine model  and construct turing mechine for identifying ones complement of  given binary number

3.Design turing machine for the following language l={0^n1^n/n>=1}

4.Design turing meching for finding 2’s complement of a given binary number.

5.what is ment by recursively enumerable language and recursive language explain with examples.

Unit 8

1   1.  Explain Chomsky hierarchy of languages and linear vounded automata

2   2.       Explain unrestricted grammar, context sensitive grammar and linear bounded automata

3    3.       Ecplain p and np problems,np compete and np hard problems

4   4.       What is meant by decidable and un decidable problems.explain with examples

5    5.       What is meant by un decidable problem. Explain posts correspondence problem .check whether the following pcp is having a solution or not

List a                                                      list b

11.                                a                                                              aaa

22.                               abaaa                                                    ab

33.                                ab                                                           b

download