Birla Institute of Technology and Science, Pilani

CS F351, Theory of Computation

Practice Questions on Regular Languages

1) Make a DFSM to accept language defined by each of the following regular expression:
i) (aba U aabaa)* ii) (ab)*(aab)*
2) Construct NFA accepting all string (a's & b's). Reading from RHS 3rd input symbol should be 'a'.
Convert the above NFA into DFA.
3) Find the regular expression that generate a string of alphabet {a,b}, where each string have
even number of 0's followed by an odd number of 1's.
4) L = {wxwR | w,x ϵ {0,1}+}. Is L a regular language.
5) Make a DFA which accepts string from {a,b}* satisfying below conditions
i) Each string has exactly 2 a’s and length of the string is divisible by 3.
6) Find the number of state in minimal DFA that accept all the string of {0,1}*, where every string
start with “10” and the length of string is congruent (0 mod 3).
7) Write a regular expression where no two a’s and no two b’s come together.
8) Make regular expression for L = {0m1n | m+n=odd}.
9) Consider two regular expression P and Q where P={(01)*+1}* and Q={(01)*(1(01)*)*}.
Find the relation between them:
a) P==Q
b) P is a subset of Q.
c) Q is a subset of P.
d) none.

11) Make i) DFA F1 = {w 𝛜 {0,1}}*| #0(w) is divisible by 3 and #1(w) is divisible by 5}

10) r = ( bb * a ) * bb * ( a + b ) b * make DFA for the given expression.

ii) DFA F2 = {w 𝛜 {0,1}}*| #0(w) is even and #1(w) is odd}

Make F3 = F1 ⋂ F2.
12) Convert given NFA-^ to DFA :

13) i) Which language does the DFA accept? ii) Specify a regular grammar, which generates the
same language.

14) Write a Regular Expression for a string made up of {0,1}* :

 i) String must end with 101 and ii) Shouldn't have 010 as subsrting.
15) Draw the NFA for that recognizes the set of strings on the alphabet {0, 1} that start and end
with a 1, and in which
every 0 is immediately preceded by at least two 1’s.
16) Draw the NFA for following language on the alphabet {0} L = { {0 k : k mod 2 = 0 or k mod =
3} }
17) Design DFA’s (Mealy Model) which will increment the given binary number by 1, with the least
significant bit being
read first and most significant bit last.
18) For the following FA find the minimized FA accepting the same language:

19) Draw DFA for the following language on Σ = {a,b}, L = { w : n a(w)mod 3 > nb(w)mod 3 }
20) Convert NFA to a right-linear grammar:

Q1)
Let L be a regular set over an alphabet Σ. Which of the following are
regular? Justify your answers.
(a) suff (L) = {v | ∃u ∈ Σ∗: uv ∈ L}
(b) mid-thirds(L) = {v | ∃u, w : |u| = |v| = |w| and uvw ∈ L}.

Q2)
Consider the following non-deterministic finite automaton (NFA) over the alphabet Σ = {0, 1}.
Give a one-sentence description of the language recognized by the NFA. Write a regular
expression for this language.
Q3)
a) Given that A is regular and A∪B is regular, does it follow that B is necessarily regular? Justify
your answer.
b) Given two finite automata M1, M2, outline an algorithm to decide if L(M1) ⊆L(M2).

Q4)
What is the language generated by this regular expression ?
(b + ε ) (a + ab)*

Q5)
Let L be the language generated by regular expression 0*10* and accepted by the deterministic
finite automata M. Consider the relation R(M)defined by M. As all states are reachable from the
start state, R(M) has _____ equivalence classes.

Q6)
Consider the language F ={a^i b^j c^k | i,j,k>=0 and if i=1 then j=k }
(a) Show that F is not regular.
(b) Show that F acts like a regular language in the pumping lemma. In other words,
give a pumping length p and demonstrate that F satisfies the three conditions of the
pumping lemma for this value of p.
(c) Explain why parts (a) and (b) do not contradict the pumping lemma.

Q7)
Define an R1-tree as a tree whose interior nodes have degree 2, and whose left child is
always a leaf with value either 0 or 1. Determine if there is a regular language to describe
such trees (i.e., there is a 1-1 onto mapping from the strings in the language to R1-trees. If
there is, give the formal DFA definition and state transition diagram; if there is not, provide
a proof.

Q8)
a)Suppose there is a robot which should wander randomly through the library, and if it
finds a book not on the shelves, it should take it to the book return bin. If it gets low on
energy, it should go to an open outlet and plug in for 30 minutes. Give the formal definition,
as well as the state transition diagram, of a reasonable DFA to control this behavior.
b) Give a method by which states and transitions can be added to take care of problems
that might arise (e.g., people block passage, essential sensors fail, etc.).

Q9)
Give the formal definition (i.e., clear, detailed descriptions of all the sets and functions
in the DFA) and state diagram of a DFA to control the elevator for a building with 4 floors.
This must handle button pushes requesting up or down from any floor at any time. Discuss
the options you choose for the DFA, what role time plays, and defend your choice of input
alphabet, transition function, start and final states.

Q10)
Consider a toy, as shown on the diagram below. A marble is dropped into
the pipe A. The levers l1, l2, and l3 cause a marble to fall either left or right. Whenever a
marble encounters a lever, it causes the lever to change state, so that the next marble that
encounter the lever will fall to the opposite direction. The initial positions of the levers are
as depicted in the diagram.
Your task is to model this toy by a DFA. Denote a marble at pipe A by a 0-input, so
your input alphabet Σ is {0}. A sequence of inputs is accepted if the last marble comes out
of pipe C. For example: a sequence 0 should be rejected, a sequence 000 should be accepted.
(a) Draw the state transition diagram for DFA, and explain the meaning of the states in DFA
(b) Describe the language accepted by your DFA.
(c) Write a regular expression for the language accepted by your DFA

Q11)
Learn and understand the algorithm for minimization of DFAs .Find the minimum-state
DFA equivalent to the DFA described by the following transition diagram:

Q12)
Let M = (Q, Σ, δ, q0, F) be a DFA where Q contains k states. Show that if L(M) ≠ ∅
then L(M) must contain at least one string of length at most k − 1.

Q13)
Let P be an infinite but countable set, and associate with each p ∈ P a language Lp. The smallest
set containing every Lp is the union over the infinite set P; it will be denoted by Up∈ᴾLp. Show by
example that the family of regular languages is not closed under infinite union.

Q14)
A language is said to be a palindrome language if L = L^R. Find an algorithm for determining if a
given regular language is a palindrome language.

Q15)
In some applications, such as programs that check spelling, we may not need an exact match of
the pattern, only an approximate one. Once the notion of an approximate match has been made
precise, automata theory can be applied to construct approximate pattern matchers. As an
illustration of this, consider patterns derived from the original ones by insertion of one symbol.
Let L be a regular language on Σ and define
insert (L) = {uav : a ∈ Σ,uv ∈ L}.
In effect, insert (L) contains all the words created from L by inserting a spurious symbol
anywhere in a word.
(a) Given an nfa for L, show how one can construct an nfa for insert (L).
(b) Discuss how you might use this to write a pattern-recognition program for insert (L), using as
input a regular expression for L.

Q16)
Convert the following DFA into a regular expression using state elimination.

Q17)
Let A = (Q, S, ∆, F) be an NFA. Consider the system of equations (Eq) induced by A below:
x𝗉={ ⋃𝗊∈∆(p,a) ({a} · x𝗊) ∪ {ε} if p ∈ F,
⋃𝗊∈∆(p,a) ({a} · x𝗊) otherwise.}
Show that (Eq) has a unique solution, given by xp = Lp, where
Lp= {w ∈ Σ∗| ∃f ∈ F : p ʷ→∗f},
for each p ∈ Q.

Q18)
Consider the finite automaton given by the diagram. Is the automaton deterministic?
Using a standard method construct a regular expression for the language defined by the
automaton.

Q19)
Provide the details showing that if A and B are regular languages then the concatenation A ◦ B is a
regular language. In particular, explain how to prove that if A ◦ B is regular then there is an NFA or
DFA, C, such that any string w ∈ A ◦ B must also be in L(C) and if w ∈ L(C) then
w∈A◦B

Q20)
Design a finite state machine that finds the least significant bit in the sum of two binary numbers.
(Consider Σ = {00, 01, 10, 11} to capture all combinations of two input bits. Assume that the bits of
the input numbers are fed serially into your FSM. When LSB of the present sum is 1, your machine
must be in a final state). Note that this technique can be extended to find any bit of the sum,
essentially showing that finite automata can perform addition.
 Questions from Regular Languages

1. Construct a DFA which accept the language L = { w | w ϵ {a,b}* and na(w)

mod 3 = nb (w) mod 3 = 0}
2. Construct a DFA which accept the language L = {anbm | n >= 1, (m) mod 3 = 1}
3. Construct a DFA which accept the language L = {wwR | |w|=2, Σ={a, b}*}
4. Construct a minimal DFA accepting a set of strings over {a, b} in which the
second symbol from left-hand side is always ‘b’.
5. Construct a minimal DFA accepting a set of strings over {a, b} in which the
third symbol from left-hand side is always ‘b’.
6. Construct a minimal DFA accepting set of strings over {a, b} in which every
‘a’ is followed by a ‘b’.
7. Construct a minimal DFA accepting set of strings over {a, b} in which every
‘a’ is never followed by ‘b’.
8. Construct a minimal DFA accepting the language L = {abwba | w ϵ {a, b}*}.
9. Construct a DFA for the set of string over {a, b} such that length of the string |
w| is divisible by 3 i.e, |w| mod 3 = 0.
10. Construct a minimal DFA accepting set of strings over {a, b} in which
Number of a(w) mod 2 = 0 or Number of b(w) mod 2 = 0 i.e, number of ‘a’
should be divisible by 2 or number of ‘b’ should be divisible by 2 or both are
divisible by 2, where ‘w’ is the any string over {a, b}.
11. Construct DFA for strings not containing consecutive two a’s and starting
with a.
12. Draw DFA of the language containing the set of all strings over {a, b} in
which 2nd symbol from RHS is ‘a’.
13. Draw DFA of the language containing the set of all strings over {a, b} in
which 3rd symbol from RHS is ‘a’.
14. Design a DFA for accepting the language L = {ambn | (m+n) is even }
15. Design a DFA for accepting the language L = {ambn | (m+n) is odd }
16. Construct a DFA accepting the strings over {0, 1} which when interpreted as
binary number is divisible by 2.
17. Construct a DFA accepting the strings over {0, 1} which when interpreted as
binary number is divisible by 3.
18. Draw DFA of the language containing the set of all strings over {a, b} in
which the starting and ending symbols are same.
19. Draw DFA of the language containing the set of all strings over {a, b} in
which the starting and ending symbols are different.
20. Design a DFA for accepting the language L = { an | n >= 0, n != 3}
21. Design a DFA for accepting the language L = { an | n >= 0, n != 2 and n != 4}
22. Construct a DFA for the regular expression (b|ab*ab*)*
23. Construct a DFA for the regular expression (a|b)*ab(a|b)*
24. Construct a DFA for the regular expression (0|1(01*0)*1)*
25. Construct a DFA for the regular expression (b*ab*ab*)
26. Construct a DFA for the regular expression b*aa(a+b)*+b*ab*aa(a+b*)
27. Construct a DFA for the regular expression (a+b)(a+b)(a+b)*
28. Construct a DFA for the regular expression ((a+b)(a+b))*(a+b)
29. Construct a DFA for the regular expression (a + b)*abba
30. Construct a DFA for the regular expression (0 + 1)*0011
31. Construct Regular Expression from the following DFA:

32. Construct Regular Expression from the following DFA:

33. Construct Regular Expression from the following DFA:

34. Construct Regular Expression from the following DFA:

35. Construct Regular Expression from the following DFA:

1) Write Regular Expression for the Language L

L = { w : w ∈ {a,b}*, |w| is odd, w has exactly one b}

2) Draw DFA for the following Regular Expression

(a+ba)(a+ba)*

3) Draw DFA for the following Regular Expression

a*b*

4) Write Regular Expression for the Language L Over

L = { w : w ∈ {a,b}*, no 2 a's and no 2 b’s should come together }

5) check whether the Language L = { wxwR | w , x ∈ (0,1)+ }

is regular or not and if it is give Regular Expression also

Note) Here wR denotes the reverse of string of w.

6) Draw DFA for the following Regular Expression

( ab )* + ( a + ab* )* + ( a + a b)* b*( a + b)*

7) Given a language L define Li as follows:

L 0 = {ε}
L i = Li-1 . L for all i>0
 The order of a language L is defined as the smallest k such that L k = Lk+1 .

Consider the language L1 (over alphabet 0) accepted by the following

automaton.

The order of L1 is ___

Note ) Here . represents concatenation

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

Notes : (write answer in terms of k or n )

9) How many DFA's exist with n states over the m input alphabet ?

10) Write Regular Expression for the Language

S1 = { (an)m | n≤ m ≥0 }

S2: { anbn | n ≥ 1 } ∪ { anbm | n ≥ 1 , m ≥ 1 }

Note) Here ∪ denote mathematical Union Operation

11) Given L1 = a*baa*

L2 = ab*

The regular expression corresponding to language

L3 = L1 / L2 (right quotient) is given by

12) Is this language a regular language? if yes give Regular Expression

L = {ambn | m-n = even }

13) Let L= { bitspilani } over alphabets Σ={a,b,i,l,n,t,p,s},

L1 = prefix(L) and

L2=L1 / Σ∗ .

The number of strings in L2 ( assume L1 and L2 does not include

empty string ) are ____

14) 14)which of the following is always correct

Σ∗ - { ε ) = Σ +

L* - { ε } = L+

R* - { ε } = R+

Note) Here

Σ denotes input alphabets

L denotes Language L over input alphabets

R denotes Regular Expression

15) Is this language a regular language? if yes give Regular Expression

L = { xy ∣ x, y∈ { 0, 1 }* |x|=|y| }

16) Let Σ be the set of all bijections from {1,...,5} to {1,...,5}, where id
denotes the identity function
 i.e. id(j) = j , ∀j.
Let ∘ denote composition on functions.
For a string x = x1 x2 ...xn ∈ Σn , n≥0,
let π(x) = x1 ∘x2 ∘⋯∘xn
Consider the language L = { x∈Σ* ∣ π(x) = id }.

The minimum number of states in any DFA accepting L is _______

17) Let P , Q , R be a regular expression over Σ.

If P does not contain null string ,
then R = Q+RP, has a unique solution

Find that unique solution

18) check whether given Language

L = { anbmcp | n+m+p > 5 } is regular or not

If yes then justify your answer

19) Construct a minimal DFA which accepts set of all strings over { a, b }

such that second symbol from RHS is 'a'.

20) Consider the following subsets of { a,b,$}*

A = { xy | x,y ∈ {a,b}* , #a(x) = #b(y) }

B = { x$y | x,y ∈ {a,b}* , #a(x) = #b(y) }

Which of the above two languages are regular justify your answer

Write also the Regular expression for the Language which is/are regular

Note) Here #a(x) denotes number of a’s in x

And #b(y) denotes number of b’s in y