THEORY OF COMPUTATION

(Regular Languages, Finite Automata, Regular Expressions)

SOLUTIONS

1. A minimal DFA accepting the language L = {w⁄w ∈ (0,1)∗ }, the number of a’s, b’s and c’s in
w are divisible by 2, 3 and 4 respectively has ________ number of states

Solution: 24.72 To 23.28

Explanation:

We first consider three DFA’s, F1, F2 and F3 for accepting strings with number of a’s divisible
by 2, number of b’s divisible by 3 and number of c’s divisible by 4 respectively. Each FA has 2,
3 and 4 states respectively. To obtain a DFA which accepts L, we do Cartesian product of F1, F2
and F3 that gives 24 states (2x3x4).

So, the minimized automata which accepts our language contains only 24 states.

2. Consider the language L1 = {ap ∙ b q ∙ c r | p, q, r > 0} and L2 = {ap ∙ b q ∙ c r | p, q, r ≥

0 and p = r}, then which of the following statements are true.

(1) L1 ∪ L2 is a context free language

(2) L1 ∩ L2 is a context free language
(3) L1 ⎼ L2 is not regular
(4) L1 and L2 both are regular languages

(a) Only 1 and 2 statements are true (b) Only 3 and 4 statements are true
(c) Only 1, 2, 3 statements are true (d) Only 1, 2, 4 statements are true

Solution: Option (c)

Explanation:

For the given language of L1 and L2,

L1 is regular and L2 is context free

Consider the statements:

(1) The union of L1 and L2 i.e., union at Regular and context free is context free language.
Statement 1 is true.

1
(2) The intersection of L1 and L2 i.e., intersection of Regular and context free is context free
language. Statement 2 is true.

(3) L1 – L2 ={apbqcr/p!=r, p,q,r>0} which is clearly cannot be accepted by DFA. Its DCFL.

(4) L1 is regular and L2 is not regular. Therefore statement 4 is false

3. Find the number of states in minimal finite automata which accepts a language of strings
whose length divisible by both ‘5’ and ‘2’ over Σ = {0, 1}

Solution: From 10.3 To 9.7

Explanation:

Any number which is divisible by both 5 and 2 is L.C.M. (2, 5) is 10

∴ The number which is multiplies at 10 is divisible by both 5 and 2

∴ And the number multiple at ‘10’, is also will divisible by 5 and 2

∴ If the length of the string is divides by ‘10’ it will produces residue 0 to 9

∴ For representing each residue we require one state each

∴ Total number of M.F.A. contains ‘10’ states

4. Find minimized finite automata which recognizes the below languages, separately by m1 and
m2 over binary strings as input, then find the number of states in each of the following.

L1:L2 is a language, which contains a set of strings which produces a remainder ‘1’, when its
equivalent value is divisible by ‘4’.

L2:L1 is a language it contains a set of strings which are starting with 1010 and the length of the
string is divisible by 4.

(a) m1 contains 4 states and m2 contains 7 states

(b) m1 contains 4 states and m2 contains 8 states
(c) m1 contains 3 states and m2 contains 9 states
(d) m1 contains 4 states and m2 contains 9 states

Solution: Option (c)

Explanation:

2
Given that the input for the finite automata is binary strings i.e., Σ = {0, 1}

L1:L2 is a language which contains a set of strings which produces remainder ‘1’ when its
divisible by 4.

int = 1(mod 4), when any number is divisible by 4 its produces remain 0 (or) 1 (or) 2 (or) 3,
for each remainder we are taking one state i.e., q0, q1, q2, q3

Above is the transition table for our language q0 is the initial state and q1 is final state because its
produces resident.

 In the above transition table, the behavior at q0 and q2 is same and q1 and q3 is same
 So, we can merge q0 and q2 states because both are non-final states, coming to q1 and q3
merging is not possible because one is final state and the other is non-final
 After merging q0 and q2 (i.e. q0 = q2), the transition table and diagram becomes

In above diagram it contains 3 states only.

 L2:L1 is a language in which all strings are starting with 1010 and whose length is
divisible by 4

3
The number of states in above automata is 9

5. Construct a minimal finite automata for the language ‘L’, it contains a set of strings, which are
having two consecutive 0’s and the number of 0’s in the same string is divisible by ‘2’.

Solution: From 6.18 To 5.82

Explanation:

Minimal finite automata for language L, in which all strings contains two consecutive 0’s and
number of 0’s is divisible by 2.

Consider 𝐿 = 𝐿1 ∩ 𝐿2

L1 contains strings which are having 2 consecutive 0’s

L2 contains strings, where number of 0’s in the string is divisible by 2

The Cartesian product of m1 and m2 is

4
Is the above table, no state have the same behavior so, we cannot minimize it and q2p0 is the final
state because q2 is final in m1 and po is final in m2. (which recognized the strings both in L1 and
L2 i.e., L1 ∩ L2)

∴ The total number of states in above automata is 6.

6. Consider the following two machines A and B. Suppose that an input string is processed on A
and then the output string is immediately fed into B (as Input) 2 processed only this second
resultant output is considered that the final output of AB. If the output string is same as the
original input string, we say that AB has identity property symbolically written (A) (B) = identity

Which of the following is correct?

(a) (A) (B) = (B) (A) (b) (B) is inverse machine of (A)

5
(c) (A) is inverse machine of (B) (d) All are true

Solution: Option (b)

Explanation:

Suppose input is 01010 gives on A.

Then output is 1 1 0 1 0

Gives as a input on B

Then output is 0 0 1 0 1

So output of B

Always invert the output of A

7. The language accepted by below automata is

(a) L = {ax bbx ⎸x ≥ 0 } (b) L = {ax b ∪ b ⎸ x ≥ 0}

(c) L = {ax bx ∪ b ⎸x ≥ 0} (d) L = {ax b ∪ abx ⎸x ≥ 0}

Solution: Option (d)

Explanation:

Language accepted by below automata is

6
Consider option (a)

L = {ax bbx ⎸x ≥ 0 }
let x = 2, a2bb2 ∈ L
∴ aabbb

Apply this string in automata, it is not accepted by our automata (it will go to dead state)
∴ option (a) is wrong

Consider option (b)

L = {ax b ∪ b ⎸ x ≥ 0}
∴ L = {b, ab, aab, aaab, ……….}

 If the automata is constructed for only this language, then the strings does not belongs to
L should not be accept
 but the string abbb ∈ L is also accepting
 So, option (b) is wrong
∴ option (d) is the Right answer

Consider option (c)

L = {ax bx ∪ b ⎸x ≥ 0}
Consider a string in this language
aabb ∈ L

 Apply this string in the given automata it will reject by our automata. So, the given
automata is not for this language

Consider option (d)

L = {ax b ∪ abx ⎸x ≥ 0}
∴ L = {b, ab, aab, ……., a, ab, abb, abbb……}

7
Above strings are accepted by our given automata

 The strings which does not belongs to L i.e., aabb ∉ L is rejected by our automata.

8. Consider the language defined by the regular expression (a | b) * b+.

Which of the following regular expressions also define that language?

(i) (a*b+) | (b*b+)

(ii) (ab |bb)*b*
(iii) (a | b | ba)*b+

(a) i only (b) i & ii only

(c) iii only (d) All of these

Solution: Option (c)

Explanation:

L = (a | b) * b+ ⇒ generate all string that end with b

abab

(i) (a*b+) | (b*b+) Does not generate but generated by L

(ii) (ab |bb)*b* Generates λ but not generated by L
+
(iii) (a | b | ba)*b ≡ L

9. Find the Regular expression for the following F.A.

(a) (a + b + c) ∙ (a + b + c)∗ ((a + c)∗ + (b + c)∗ + (a + b)∗ )

(b) (a∗ + b∗ + c ∗ ) ∙ ((bc)∗ + (ac)∗ + (ab)∗ )

8
(c) (a+ (a + b + c)∗ ∙ ((b + c)∗ ) + (b+ ∙ (a + b + c)∗ ∙ (a + c)∗ ) + (c + ∙ (a + b + c)∗ ∙ (a + b)∗ )
∗ ∗ ∗
(d) (a+ ((b + c)a) ∙ (b + c + ) + (b+ ∙ ((a + c)b) ∙ (a + c)∗ ) + (c + ∙ ((a + b) ∙ c) ∙ (a + b)+ )

Solution: Option (d)

Explanation:

The Regular expression for the given finite automata is

The language accepted by this automata is

 The strings in the language does not having starting and ending with same symbol. It
means if any string starts with ‘a’ it should end with ‘b’ (or ) ‘c’ (or) if the string
starts with ‘b’ it should ends with ‘a’ or ‘c’ (or) if the string is starts with ‘c’, it should
end with ‘b’ or ‘c’.

∴ L = (ab, ac, aab, aac, abb, abc, acb, acc, …………….

ba, bc, bba, bbc, baa, bac, bca, bcc, …………….
ca, cb, caa, cab, cba, abb, cca, ccc, …………….}

Consider a given option (a):

(a + b + c) ∙ (a + b + c)∗ ∙ (a + c)∗ + (b + c)∗ + (a + b)∗

This regular expression may generate ‘a’ and ‘aa’ also, but both the strings are not accepted by
our automata.

∴ option a is wrong answer

Consider option (b):

9
(a∗ + b∗ + c ∗ ) ∙ ((bc)∗ + (ac)∗ + (ab)∗ ). This regular expression may generate ∈, a, aa, bb, cc
also. These also strings are not accepted by our given automata.

∴ option ‘b’ is wrong answer.

Consider option (c):

(a+ (a + b + c)∗ (b + c)∗ ) + (b+ ∙ (a + b + c)∗ ∙ (a + c)∗ ) + (c + ∙ (a + b + c)∗ ∙ (a + b)∗ ). This

regular expression may generate ‘a’, b, a, aa, bb, cc also. These all strings will be rejected by our
given automata.

Consider option (d):

∗ ∗ ∗
(a+ ((b + c)a) ∙ (b + c + ) + (b+ ∙ ((a + c)b) ∙ (a + c)∗ ) + (c + ∙ ((a + b) ∙ c) ∙ (a + b)+ ).
This regular expression will generate a string with minimum length ‘2’.

∴ L = {ab, ac, ba, bc, ca, cb, …..aab, aac, bba, bbc, cca, ccb, ….. abab, acac, baba, babc, …….}
The above all strings are accepted by our given automata.

∴ option (d) is right answer.

10. Below is the grammar then find the language generated by given grammar

S → ABC Xb → bx
AB → aAx |bAy | ∊ Ya → ay
C→∊ Yb → by
XC → BaC aB → Ba
YC → BbC bB → Bb
Xa → aX

(a) L = {w|w ∈ (a, b)∗ , and xa (w) = xb (w)}

(b) L = {w|w ⊆ (a, b)+ , and w is a palandrom string
(c) L = {w|w ⊆ (a, b)∗ , and w = xx, where X = (a, b)∗}
(d) None of the above

Solution: Option (c)

Explanation:

Given grammar is
S → ABC Xb → bx
AB → aAx |bAy | ∊ Ya → ay

10
C→∊ Yb → by
XC → BaC aB → Ba
YC → BbC bB → Bb
Xa → aX

Generate same string randomly

S → ABC
→ aAxC
→ aABaC
→ a∙∊ ∙ a∙∊
→ a∙a

(2) S → ABC

S → aAxC
S → aABaC
→ abAyaC
→ abAayC
→ abAaBbC
→ abABabC
→ ab∊∙ab∙∊
→ ab∙ab

S → ABC
→ bAyC
→ bABbC
→ bbAybC
→ bbAbyC
→ bbAbBbC
→ bbABbbC
→ bbaAxbbC
→ bbaAbxbC
→ bbaAbbxC
→ bbaAbbBbaC
→ bbaAbBbaC
→ bbaABbbaC
→ bba∙∊∙bba∙∊
→ bba∙bba

See above all strings which are generated from out grammar, those are in the form of

11
w ∙ w|w ∈ (a, b)∗

∴ Consider option (c)

i. e. , L = {w|w ⊆ (a, b)∗ and w = x ∙ x and x ∈ (a, b)∗ }

∴ Option (c) is right answer.

12