1 consider the language l o i j j i 0 j 0 i j 2 a classify the language as regu 5346446

1. Consider the language

L = {Oⁱ j^j | i ≥ 0, ≥ j≥ 0, | i – j = 2}

a) Classify the language as regular, context free or non contextfree. Give the most precise classification for the language. i.e.every regular language is also context free, but a context freelanguage may not be regular

b) If the language is regular- give the equivalent regularexpression, if it is context free- give grammar producing thelanguage, if it is not context free-prove that.

2. Construct the Chomsky normal form for the given grammar

           S –> 0A0|1B1|BB

           A –> C

           B –> S|A

           C–> S|ε

b) Give a parse tree (with respect to the CNF grammar) of thestring 0100101111.

3. For each of the five statements below, determine whether theyare true or false and give brief but solid justification for youranswer.

a) The pumping lemma for regular languages and context freelanguages are the same.

b) The context-free languages are closed under intersection.

c) For any given PDA(push down Automaton) the language that itaccepts by final state.

d) Regular languages are closed under complementation.

e) There is a polynomial time algorithm that decided whether twocontext free language have some strings in common.

4) State, without proof, the algorithmic complexity. (decidablein polynomial time, decidable in exponential time, or undecidable)of the following two problems.

a) Testing a membership of a string w in a context- freelanguage L.

b) Conversion between a finite automaton A and itsequivalent regular expression R_A.

5a) Give complete formal definition of the transition functionPDA. Introduce and explain all necessary terms and conditions.

b) Explain briefly, but precisely and clarly the man differencebetween PDA and NDFA

6) Contruct the Greibach normal form for the given grammar

    S –> 0A0|1B1|BB

    A –> C

    B –> S|A

    C –> S|ε

b) Give a parse tree (with respect to the CNF grammar) of thestring 0100101111.

7) Consider the language L = {aⁿ bⁿcⁱ | i ≤ n}

a) Classify the language as a regular context free or noncontext free. Give the most precise classification for the languagei.e every regular language is almost context free, but a contextfree language may not be regular,

b) if the language is regular – give the equivalent Regular expression, if it is context free – give the grammarproducing the language, if it is not context free – provethat.

8) For each of the five statement below, determine whetherthey are True or False and give brief, but sold justification foryour answer.

a) Test strings for membership in a context free language can bedone in polynomial time with respect to the size of the string.

b) The context free language are closed under complement.

c) for any given PDA the language that it accepts by empty stackis always the same as the language it accepts by final state.

d) Regular language are closed under intersection.

e) There is a polynomial time algorithm that decides whether twocontext free languages have some string in common.