Automata Questions with Answers Set-2

This post contains a computer network related to 20 multiple-choice questions (Automata SET-2) that help you to go through the subject and prepare you for Automata-related questions in competitive exams.

Table of Contents

Toggle

Automata MCQ Test Series Set-2

Automata MCQ Test Series Set-2

Total Number of Questions: 20
Each question carries equal marks i.e 1
No Negative Marking

Page 1 of 2

1. The set of all recursively enumerable languages is

A.closed under complementation.

B.closed under intersection.

C.a subset of the set of all recursive languages.

D.an uncountable set.

2. Which one of the following statements is FALSE?

A.Context-free grammar can be used to specify both lexical and syntax rules.

B.Type checking is done before parsing.

C.High-level language programs can be translated to different Intermediate Representations.

D.Arguments to a function can be passed using the program stack.

Consider the following context-free grammar over the alphabet $\sum = \left\{ a,b,c \right\}$ with S as the start symbol:

$S\to abST |abcT$
$T\to bT |b$

Which one of the following represents the language generated by the above grammar?

A.$\left\{(ab)^{n}(cb)^{n}|n\ge 1 \right\}$

B.$(ab)^{n}cb^{m_{1}}cb^{m_{2}}........cb^{m_{n}}|n,m_{1},m_{2},......,m_{n}\ge 1$

C.$\left\{(ab)^{n}(cb^{m})^{n}|m,n\ge 1 \right\}$

D.$\left\{(ab)^{n}(cb^{n})^{m}|m,n\ge 1 \right\}$

For $\Sigma = {a,b}$, let us consider the regular language L= $\left\{ x|x = a^{2+3k}or x = B^{10+12k},k\ge 0 \right\}$ Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?

A.3

B.5

C.9

D.24

5. Which of the following languages is generated by the given grammar?

$S\to aS|bS|\varepsilon$

A.{a,b}*

B.$\left\{ a^{n}b^{m}|n,m\ge 0 \right\}$

C.$\left\{ w\in \left\{ a,b \right\} ^{*}\right\}$ has equal number of a' s and b's

D.$\left\{ a^{n}|n\ge 0 \right\}\cup \left\{ b^{n} |n\ge 0\right\}\cup \left\{ n\ge 0 \right\}$

Consider the following grammar :

$ P\rightarrow xQRS $

$ Q\rightarrow yz|z $

$ R\rightarrow w|\epsilon $

$ S\rightarrow y $

Which is FOLLOW(Q)?

A.{R}

B.{w}

C.{ w, y }

D.{w,$}

7. Which of the following decision problems are undecidable?

Given NFAs $N_{1} and N_{2}, is L(N_{1}) \cap L(N_{2}) = \phi$
Given a CFG G = $(N,\sum, P, S)$ and a string x $\in \sum^{*}$ , does x $ \in $L(G) ?
Given CFGs $G_{1}$ and $G_{2}$ is L$(G_{1})$ = L $(G_{2})$ ?
Given a TM M, is L(M) = $\phi$

A.1 and 4 only

B.2 and 3 only

C.3 and 4 only

D.2 and 4 only

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

A.(0+1)*0011(0+1) *+(0+1) *1100(0+1) *

B.(0+1) * (00(0+1) *11+11(0+1) *00)(0+1) *

C.(0+1) *00(0+1) *+(0+1) *11(0+1) *

D.00(0+1) *11+11(0+1) *00

Which one of the following languages over $\Sigma$ = {a,b} is NOT context-free?

A.$\left\{ ww^{R}|w\in \left\{ a,b \right\}^{*} \right\}$

B.$\left\{ wa^{n}b^{n}w^{R}|w\in \left\{ a,b \right\}^{*}, n\ge 0 \right\}$

C.$\left\{ wa^{n}w^{R}b^{n}|w\in \left\{ a,b \right\}^{*}, n\ge 0 \right\}$

D.$\left\{ a^{n}b^{i} |i\in \left\{ n,3n,5n \right\}^{*},n\ge 0\right\}$

10. Consider the following language:

I. $(a^{m}b^{n}c^{p}d^{q}|m+p = n+q, $ where $ m,n,p,q\ge 0)$

II. $(a^{m}b^{n}c^{p}d^{q}|m=n $ and $ p = q, $ where $ m,n,p,q\ge 0 )$

III. $(a^{m}b^{n}c^{p}d^{q}| m= n = p $ and $ p \neq q $, where $ m,n,p,q\ge 0)$

IV. $(a^{m}b^{n}c^{p}d^{q}|mn = p+q,$ where $ m,n,p,q\ge 0)$

Which of the languages above are context-free?

A.I and IV only

B.I and II only

C.II and III only

D.II and IV only

Page 2 of 2

11. Consider the following sets:

S1. Set of all recursively enumerable languages over the alphabet {0,1}

S2. Set of all syntactically valid C programs

S3. Set of all languages over the alphabet {0,1}

S4. Set of all non-regular languages over the alphabet {0,1}

Which of the above sets are uncountable?

A.S1 and S2

B.S3 and S4

C.S2 and S3

D.S1 and S4

12. Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a Machine M.

(I) For an unrestricted grammar G and a string w, whether $w\in L(G) $

(II) Given a Turing machine M, whether L(M) is regular.

(III) Given two grammars $G_{1}$ and $G_{2}$ , whether L($G_{1}$) = L($G_{2}$)

(IV) Given an NFA N, whether there us a deterministic PDA P such that N and P accept the same language.

Which one of the following statements is correct?

A.Only I and II are undecidable

B.Only III is undecidable

C.Only II and IV are undecidable

D.Only I, II and III are undecidable

13.

. If G is a grammar with productions

S $\rightarrow$ SaS | aSb | bSa | SS | $\epsilon$

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

A.abab

B.aaab

C.abbaa

D.babba

14.

Consider the context-free grammars over the alphabet {a,b,c} given below. S and T are non-terminals.

$G_{1}:S\rightarrow aSb|T,T\rightarrow cT|\epsilon$

$G_{2}:S\rightarrow bSa|T,T\rightarrow cT|\epsilon$

The language $L(G_{1})\cap L(G_{2})$ is

A.Finite

B.Not finite but regular

C.Context-Free but not regular

D.Recursive but not context-free

15. Consider the following languages over the alphabet $\sum = \left\{ a,b,c \right\} $

Let $L_{1} =\left\{ a^{n}b^{n}c^{m}|m,n\ge 0 \right\}$ and $L_{2} =\left\{ a^{m}b^{n}c^{n}|m,n\ge 0 \right\}$

Which of the following are context-free languages?

$L_{1}\cup L_{2}$

$L_{1}\cap L_{2}$

A.I only

B.II only

C.I and II

D.Neither I nor II

16.

Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let $L_{f}$ denote the language $\left\{ x \# f(x)|x\epsilon A^{*} \right\}$.

Which of the following statements is true.

A.f is computable if and only if L_{f}is recursive.

B.f is computable if and only if L_{f} is recursively enumerable.

C.f is computable then $L_{f}$ is recursive, but not conversely.

D.f is computable then $L_{f}$ is recursively enumerable, but not conversely

17.

Consider the language L given by the regular expression (a+b)*b(A+b) over the alphabet {a,b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is

A.1

B.2

C.3

D.4

18.

Consider the following context-free grammars:

$G_{1}:S\to aS |B, B\to b |bB$

$G_{2}:S\to aA|bB , A \to aA|B|\varepsilon, B \to bB | \varepsilon$

Which one of the following pairs of languages is generated by $G_{1}$ and $G_{2}$, respectively?

A.$\left\{ a^{m}b^{n}|m\gt 0 or n\gt 0 \right\}$ and $\left\{ a^{m}b^{n}|m\gt 0 or n\gt 0 \right\}$

B.$\left\{ a^{m}b^{n}|m\gt 0 or n\gt 0 \right\}$ and $\left\{ a^{m}b^{n}|m\gt 0 or n\ge 0 \right\}$

C.$\left\{ a^{m}b^{n}|m\ge 0 or n\gt 0 \right\}$ and $\left\{ a^{m}b^{n}|m\gt 0 or n\ge 0 \right\}$

D.$\left\{ a^{m}b^{n}|m\ge 0 or n\gt 0 \right\}$ and $\left\{ a^{m}b^{n}|m\gt 0 or n\gt 0 \right\}$

19.

Consider the following grammar :

Stmt $\to$ if expr then expr else expr; stmt | o

Expr $\to$ term relop term | term

Term $\to$ id | number

id $\to$ a | b | c

Number $\to$ [0-9]

Where relop is a relational operator (e.g., <, >.……). 0 refers to the empty statement, and if, then, else are terminals.

Consider a program P following the above grammar containing ten if terminals. The number of control flow paths in P is________.

For example, the program

If $e_{1}$ then $e_{2}$ else $e_{3}$

has 2 control flow paths, $e_{1} \to e_{2}$ and $e_{1} \to e_{3}$

A.512

B.256

C.1024

D.2056

20.

Given the language L, define $L^{i}$ as follows:

$L^{0} = {{\in }}$

$L^{i}=L^{i-1}$.L for all i>0

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 ____.

A.2

B.1

C.3

D.4

Automata MCQ Test Series Set-2

Total Number of Questions: 20

Each question carries equal marks i.e 1

No Negative Marking

Related