Solution

TM = PDA(with stack memory) + 1 extra memory

Since TM is more powerful than PDA hence we can use TM also to recognize CFL.

So S1 is true.

S2: Since CFG (type 2 ) generates CFL and every regular is CFL also, so a CFG can generate a regular language.

For ex: The below given CFG generate a regular language

S-> aAb | bAa

A-> aA | bA| ε

It generates the language strings start and end with different symbols (which is regular).

Solution

A production A→B is known as unit production, hence G1 doesn’t have any unit production. Unit production is not allowed in CNF , so G2 is not in CNF form. G1 and G2 are equivalent. Both are not in GNF form.

Solution

In CNF a CFG can have only two type of productions,

A-> BC

A->a

Hence derivation tree of strings are always binary tree. So the number of steps required to derive a string of |w| is 2|w|-1

For illustration see the example given below, which shows the derivation of a string for a CFG in CNF:

S → AB| b

A → BC| a

B → b

C → c

String: “bcb”

|w| = 3

No. of steps required:

Step 1 → S → AB

Step 2 → A → BC

Step 3 → B → b

Step 4 → C → c

Step 5 → B → b

So total steps ⇒ 2|w| - 1

⇒ 2×3-1 = 5

The given string | w| = |aaababbb| = 8

Hence it will require 2×8 -1 = 15 steps

Solution

Solution

Each production in GNF is of the form A→aα, where a∈Σ is a terminal and α∈V* is a string of nonterminals with no restriction on the length of V*.

Since each production contains exactly one terminal, a string of length “k” will require exactly “k” steps of derivation.

Solution

L = (ab)^(2n+1) | n >0 hence L is a regular language.

Solution

Solution

Solution

Both L1 and L2 are CSL and not CFL. Both require more than one comparison at a time. They are similar to L={ p^n q^n r^n | n ≥ 0} which is CSL and not CFL.

Solution

In L1 w can be “a” or “b” as w ε {a,b} so L1 is a finite language and the strings in L1 can be {aa, bb} so L1 is a regular language.

L2 is a well known CSL.

Solution

L1 is a well known CSL and its complement is a CFL. The complement of L1 is generated by a context free grammar hence it is CFL.

The complement of L1= {all strings of odd length } U {L=uv | |u|=|v| & u ≠v}

The CFG for complement of L1 is

S → E | U | ϵ

E → AB | BA

A → ZAZ | a

B → ZBZ | b

U → ZUZ | Z

Z → a | b

Solution

In L1= {wxw^r | w ε{a,b}^+ & x ε {a,b} }, x cannot be extended hence L1 is CFL and not regular.

In L2, |x| <100, so X can extend upto length 100 and hence it is also CFL and not regular.

Solution

The grammar and S → aaBb|∊, B → aaBb|aab and S → aaBb|aab|∊, B → aaBb|aab generate “∊” hence wrong.

Solution

In the worst case prefix may equal to string itself.

So in this case

L = {w#w| x is prefix of w, where w∈{a,b}*} which is clearly CSL.

Solution