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

What is the Weightage of Regular and Contex-Free Languages, Pumping Lemma in GATE Exam?

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:S1 aS1b|ε

Language L2 is defined by the grammar:S2 abS2|ε

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. L3¯L4  is recursively enumerable

II. L2¯L3  is recursive

III.L1*L2 is context-free

IV.L1L2¯ is context-free