# GATE Questions & Answers of Regular Expressions and Finite Automata

## What is the Weightage of Regular Expressions and Finite Automata in GATE Exam?

Total 39 Questions have been asked from Regular Expressions and Finite Automata topic of Theory of Computation subject in previous GATE papers. Average marks 1.59.

Let $\mathrm\Sigma$ be the set of all bijections from {1, … , 5} to {1, … , 5}, where $id$ denotes the identity function, i.e. $id(j)=j,\;\forall j$. Let $\circ$ denote composition on functions. For a string $x=x_1\;x_2\;\dots\;x_n\in\mathrm\Sigma^n,\;n\leq0$ , let $\pi(x)=x_1\circ x_2\;\circ\dots\circ\;x_n$. Consider the language $L=\{x\in\mathrm\Sigma^\ast\vert\pi(x)=id\}$. The minimum number of states in any DFA accepting $L$ is .

Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?

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 deteninistic finite-state automaton (DFA) accepting L is __________.

The minimum possible number of states of a deterministic finite automaton that accepts the regular language $\style{font-family:'Times New Roman'}{L=\{w_1aw_2\vert w_1,\;w_2\;\in\{a,b\}\ast,\;\vert w_1\vert=2,\;\vert w_2\vert\geq3\}}$ is _________.

Let $\delta$ denote the transition function and $\widehat\delta$ denote the extended transition function of the $\style{font-family:'Times New Roman'}{\mathit\in-\mathrm{NFA}}$ whose transition table is given below:

 $\style{font-family:'Times New Roman'}\delta$ $\style{font-family:'Times New Roman'}\in$ a b $\style{font-family:'Times New Roman'}\rightarrow$q0 {q2} {q1} {q0} q1 {q2} {q2} {q3} q2 {q0} $\style{font-family:'Times New Roman'}\phi$ $\style{font-family:'Times New Roman'}\phi$ q3 $\style{font-family:'Times New Roman'}\phi$ $\style{font-family:'Times New Roman'}\phi$ {q2}

Then $\style{font-family:'Times New Roman'}{\widehat\delta(q_2,aba)}$ is

The number of states in the minimum sized DFA that accepts the language defined by the regular expression

$\left(0+1{\right)}^{\ast }\left(0+1\right)\left(0+1{\right)}^{\ast }$

is ___________.

Consider the following two statements:
I. If all states of an NFA are accepting states then the language accepted by the NFA is $\textstyle\sum_{}^\ast$.
II. There exists a regular language A such that for all languages $B$ , $\style{font-family:'Times New Roman'}{A\cap B}$ is regular.
Which one of the following is CORRECT? Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the languages L(M) $\cap$ L(N) is ________.

The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1) * (10) is _______.

Which of the following languages is/are regular?
L1:{wxwR|w, x $\in$ {a,b}* and |w|, |x| > 0},wR is the reverse of string w
L2: {anbm | m $\ne$ n and m, n $\ge$ 0}
L3: {apbqcr | p, q, r $\ge$ 0}

Let L be the language represented by the regular expression $\sum _{}^{}$* 0011$\sum _{}^{}$* where $\sum _{}^{}$ = {0, 1}. What is the minimum number of states in a DFA that recognizes $\overline{)\mathrm{L}}$ (complement of L)?

which one of the following is TRUE?

Consider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?

Which of the regular expressions given below represent the following DFA? I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1

If ,consider

(I) ${L}_{1}.{L}_{2}$ is a regular language

(I)${L}_{1}.{L}_{2}=\left\{{a}^{n}{b}^{n}|n\ge 0\right\}$

Which one of the following is CORRECT?

Let Let Which one of the following is TRUE?

The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

a*b*(ba)*a*

Consider the following languages over the alphabet $\sum =\left\{0,1,c\right\}$:

${L}_{1}=\left\{{0}^{n}{1}^{n}|n\ge 0\right\}\phantom{\rule{0ex}{0ex}}$
${L}_{2}=\left\{wc{w}^{r}|w\in {\left\{0,1\right\}}^{*}\right\}\phantom{\rule{0ex}{0ex}}$
${L}_{3}=\left\{w{w}^{r}|w\in \left\{0,1\right\}*\right\}$

Here, wr is the reverse of the string w. Which of these languages are deterministic Context-free languages?

Consider the languages ${L}_{1}=\mathrm{\Phi }$ and ${L}_{2}=\left\{a\right\}$. Which one of the following represents ${L}_{1}{L}_{2}^{\ast }\cup {L}_{1}^{\ast }$?

Consider the DFA A given below. Which of the following are FALSE?
1. Complement of L(A) is context-free.
2. L(A) = L((11*0+0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma$ = {a} and $\epsilon$ is the empty string. Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are

The lexical analysis for a modem computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Let P be a regular language and Q be a context-free language such that Q $\overline{)\subset }$ P. (For example, let P be the language represented by the regular expression p* q* and Q be { pn qn | n $\in$ $\mathbb{N}$}). Then which of the following is ALWAYS regular?

Definition of a language L with alphabet {a} is given as following.
L = {ank | k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?

A deterministic finite automaton (DFA) D with alphabet ∑ = {a, b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

Let L = {w ∈ (0 + 1)*|w has even number of |s|, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?

Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? The above DFA accepts the set of all strings over {0,1} that

Given below are two finite state automata ( $\to$ indicates the start state and F indicates a final state)

Y:

 a b $\rightarrow$ 1 1 2 2(F) 2 1

Z:

 a b $\rightarrow$ 1 2 2 2(F) 1 1

Which of the following represents the product automaton Z×Y?

Match the following NFAs with the regular expressions they correspond to 1. $\epsilon$ + 0(01*1 + 00) * 01*
2. $\epsilon$+ 0(10 *1 + 00) * 0
3. $\epsilon$ + 0(10 *1 + 10) *1
4. $\epsilon$ + 0(10 *1 + 10) *10 *

Which of the following are regular sets?

I. {anb2m|n $\ge$ 0, m $\ge$ 0}
II. {anbm|n = 2m}
III. {anbm|n $\ne$ m}
IV. {xcy|x, y, $\in$ {a, b} *}

Which of the following is TRUE?

A minimum state deterministic finite automaton accepting the language L = {w | w $\in$ {0, 1}*, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

Which of the following languages is regular?

Consider the following Finite State Automaton: The language accepted by this automaton is given by the regular expression 