# Questions & Answers of Regular Expressions and Finite Automata

Question No. 22

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

Question No. 125

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

Question No. 139

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

Question No. 126

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

Question No. 152

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?

Question No. 49

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

Question No. 145

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

Question No. 146

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}

Question No. 232

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

Question No. 25

which one of the following is TRUE?

Question No. 26

Consider the finite automaton in the following figure.

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

Question No. 46

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

Question No. 125

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?

Question No. 146

Let Let Which one of the following is TRUE?

Question No. 225

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

a*b*(ba)*a*

Question No. 246

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?

Question No. 8

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

Question No. 33

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.

Question No. 12

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

Question No. 25

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

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

Question No. 46

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

Question No. 19

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?

Question No. 24

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?

Question No. 42

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?

Question No. 45

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?

Question No. 39

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?

Question No. 41

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?

Question No. 15

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

Question No. 41

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

Question No. 49

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?

Question No. 52

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 *

Question No. 53

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

Question No. 7

Which of the following is TRUE?

Question No. 29

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

Question No. 31

Which of the following languages is regular?

Question No. 74

Consider the following Finite State Automaton:

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