# Questions & Answers of Regular Expressions and Finite Automata

## Weightage of Regular Expressions and Finite Automata

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

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?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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}

##### Show Answer

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)?

##### Show Answer

which one of the following is TRUE?

##### Show Answer

Consider the finite automaton in the following figure.

What is the set of reachable states for the input string 0011?

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

Let Let Which one of the following is TRUE?

##### Show Answer

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

a*b*(ba)*a*

##### Show Answer

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?

##### Show Answer

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 }$?

##### Show Answer

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.

##### Show Answer

What is the complement of the language accepted by the NFA shown below? Assume $\Sigma$ = {a} and $\epsilon$ is the empty string.

##### Show Answer

Given the language L = {ab, aa, baa}, which of the following strings are in L*?

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

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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)*?

##### Show Answer

The above DFA accepts the set of all strings over {0,1} that

##### Show Answer

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?

##### Show Answer

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 *

##### Show Answer

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} *}

##### Show Answer

Which of the following is TRUE?

##### Show Answer

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

##### Show Answer

Which of the following languages is regular?

##### Show Answer

Consider the following Finite State Automaton:

The language accepted by this automaton is given by the regular expression

##### Show Answer

Consider the following Finite State Automaton:

The minimum state automaton equivalent to the above FSA has the following number of states