# Questions & Answers of Regular and Contex-Free Languages, Pumping Lemma

## Weightage of Regular and Contex-Free Languages, Pumping Lemma

Total 7 Questions have been asked from Regular and Contex-Free Languages, Pumping Lemma topic of Theory of Computation subject in previous GATE papers. Average marks 1.57.

Consider the following languages:

$\style{font-family:'Times New Roman'}{\begin{array}{l}\;\;\mathrm I.\left\{a^mb^nc^pd^q\vert m+p=n+q,\;\mathrm{where}\;m,n,p,q\geq0\right\}\\\;\mathrm{II}.\left\{a^mb^nc^pd^q\vert m=n\;\mathrm{and}\;p=q,\;\mathrm{where}\;m,n,p,q\geq0\right\}\\\mathrm{III}.\left\{a^\mathit mb^\mathit nc^\mathit pd^\mathit q\vert m=n=p\mathit\;\mathrm{and}\mathit\;p\neq q\mathit,\mathit\;\mathrm{where}\mathit\;m\mathit,n\mathit,p\mathit,q\mathit\geq\mathit0\right\}\\\mathrm{IV}.\left\{a^\mathit mb^\mathit nc^\mathit pd^\mathit q\vert mn=p+q\mathit,\mathrm{where}\mathit\;m\mathit,n\mathit,p\mathit,q\mathit\geq\mathit0\mathit\;\right\}\end{array}}$

Which of the languages above are context-free?

Given a language $L$, define $L^i$ as follows:

$\begin{array}{l}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;L^0=\left\{\varepsilon\right\}\\\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;L^i=L^{i-1}.\;L\;for\;all\;\;i>0\end{array}$

The order of a language $L$ is defined as the smallest $k$ such that $L^k=L^{k+1}.$ Consider the language $L_1$(over alphabet 0) accepted by the following automaton.

The order of $L_1$ is _____.

If G is a grammar with productions

$\style{font-family:'Times New Roman'}{S\rightarrow SaS\;\vert\;aSb\;\vert\;bSa\;\vert\;SS\;\vert\;\in}$

where S is the start variable, then which one of the following strings is not generated by G?

Consider the following languages over the alphabet $\style{font-family:'Times New Roman'}{\sum=\{a,b,c\}.}$

Let $\style{font-family:'Times New Roman'}{L_1=\{a^nb^nc^m\vert m,n\geq0\}\;and\;\;L_2=\{a^mb^nc^n\vert m,n\geq0\}.}$

Which of the following are context-free languages?

$\style{font-family:'Times New Roman'}{\begin{array}{l}\mathrm I.\;\;\;\;{\mathrm L}_1\cup\;{\mathrm L}_2\\\mathrm{II}.\;\;{\mathrm L}_1\cap\;{\mathrm L}_2\end{array}}$

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

Language L1 is defined by the grammar:

Language L2 is defined by the grammar:

Consider the following statements:

P: L1 is regular

Q: L2 is regular

Which one of the following is TRUE?

Consider the following types of languages: L1 : Regular, L2 : Context-free, L3 : Recursive, L4 : Recursively enumerable. Which of the following is/are TRUE?

I. is recursively enumerable

II. is recursive

III.${L}_{1}^{*}\cap {L}_{2}$ is context-free

IV.${L}_{1}\cup \overline{{L}_{2}}$ is context-free