## Identify-Class-Language

Question 1 |

Consider the languages L1,L2 and L3 as given below.

- L1 = {0

^{p}1

^{q}|p,q∈N},

L2 = {0

^{p}1

^{q}|p,q∈N and p=q} and

L3 = {0

^{p}1

^{q}0

^{r}|p,q,r∈N and p=q=r}.

Which of the following statements is **NOT TRUE**?

Push Down Automate (PDA) can be used to recognize L1 and L2 | |

L1 is a regular language | |

All the three languages are context free | |

Turing machines can be used to recognize all the languages |

Question 1 Explanation:

L1: regular language

L2: context free language

L3: context sensitive language

L2: context free language

L3: context sensitive language

Question 2 |

Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:

- L1 = {a

^{m}b

^{m}ca

^{n}b

^{n}| m,n ≥ 0 }

L2 = {a

^{i}b

^{j}c

^{k}| i,j,k ≥ 0 }

Then L is

Not recursive | |

Regular | |

Context free but not regular | |

Recursively enumerable but not context free |

Question 2 Explanation:

The strings in L

Clearly, L

_{1}are {c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L_{2}are {ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}Clearly, L

_{1}∩ L_{2}is {a^{x}b^{x}| x ≥0}, which is CFL but not regular.Question 3 |

Which of the following is true for the language {a^{p}|p is a prime} ?

It is not accepted by a Turing Machine | |

It is regular but not context-free
| |

It is context-free but not regular | |

It is neither regular nor context-free, but accepted by a Turing machine |

Question 3 Explanation:

Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.

Question 4 |

The language L = {0^{i}21^{i} | i≥0} over the alphabet {0, 1, 2} is:

not recursive. | |

is recursive and is a deterministic CFL.
| |

is a regular language.
| |

is not a deterministic CFL but a CFL. |

Question 4 Explanation:

We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.

There are 4 questions to complete.