Theory of computation miscellaneous Easy Questions and Answers | Page - 9

Theory of computation miscellaneous

Let L be the language represented by the regular expression
What is the minimum number of states in a DFA that recognizes L (complement of L)?

1. 4
1. 5
1. 6
1. 8

View Hint View Answer Discuss in Forum

NA

Correct Option: B

NA

Let δ denote the transition function and d denote the extended transition function of the ∈-NFA whose transition table is given below:

Then d (q₂, aba) is

1. φ
1. {q₀, q₁, q₃}
1. {q₀, q₁, q₂}
1. {q₀, q₂, q₃}

View Hint View Answer Discuss in Forum

Converting the table to a state diagram then we get.

then, δ̂= (q₂ aba) All states reachable from q₂ by aba.
If aba is broken as ∈ , a , ∈ , ∈ , b , a then from q₂ it can reach q₁ and from there by null transaction to reach state q₂ as well as q₀.
Consider, (q₂ , a) = (q₂ , ∈ a) = {q₁ , q₂ q₀}.
(q₂ , ab) = (q₁ , b) = {q₀ , q₃ , q₂}
(q₂ , b) = {q₀ , q₂}
(q₀ , b) = {q₀ , q₂}
(q₂ , aba) = (q₀ , a) = {q₁ , q₂ , q₀}
(q₁ , a) = {q₂ , q₀}
(q₂ , a) = {q₁ , q₂ , q₀}
(q₃ , a) = {q₃}
Then, δ̂= (q₂ aba) = {q₁ , q₂ , q₀}
= {q₀ , q₁ , q₂}
Hence option (c) is correct.

Correct Option: C

Converting the table to a state diagram then we get.

then, δ̂= (q₂ aba) All states reachable from q₂ by aba.
If aba is broken as ∈ , a , ∈ , ∈ , b , a then from q₂ it can reach q₁ and from there by null transaction to reach state q₂ as well as q₀.
Consider, (q₂ , a) = (q₂ , ∈ a) = {q₁ , q₂ q₀}.
(q₂ , ab) = (q₁ , b) = {q₀ , q₃ , q₂}
(q₂ , b) = {q₀ , q₂}
(q₀ , b) = {q₀ , q₂}
(q₂ , aba) = (q₀ , a) = {q₁ , q₂ , q₀}
(q₁ , a) = {q₂ , q₀}
(q₂ , a) = {q₁ , q₂ , q₀}
(q₃ , a) = {q₃}
Then, δ̂= (q₂ aba) = {q₁ , q₂ , q₀}
= {q₀ , q₁ , q₂}
Hence option (c) is correct.

Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?

1. (0+1)*0011(0+1)*+(0+1)*1100(0+1)*
1. (0+1)*(00(0+1)*11+11(0+1)*00)(0+1)*
1. (0+1)*00(0+1)*+(0+1)*11(0+1)*
1. 00(0+1)*11+11(0+1)*00

View Hint View Answer Discuss in Forum

Option (a) contains 00 and 11 consecutively which does not fulfill the required condition. Option (c) does not give assurance that both 00 and 11 will be exist in the string. According to option (d), string should start with 11 and ends with 00 or vice versa. Hence option (b) is the correct answer.

Correct Option: B

Option (a) contains 00 and 11 consecutively which does not fulfill the required condition. Option (c) does not give assurance that both 00 and 11 will be exist in the string. According to option (d), string should start with 11 and ends with 00 or vice versa. Hence option (b) is the correct answer.

The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0 + 1) * (0 + 1) (0 + 1)* is ________.

1. 0
1. 1
1. 2
1. 3

View Hint View Answer Discuss in Forum

So, the minimum number of states is 2.

Correct Option: C

So, the minimum number of states is 2.

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 deterministic finite-state automata (DFA) accepting L is ________.

1. 2
1. 4
1. 1
1. 10

View Hint View Answer Discuss in Forum

The given regular expression is (a + b) * b (a + b). In this all string whose second last bit is ‘b’. So, the minimal NFA is

It can be described as “All string over {a, b} ending with ‘ba’ or ‘bb’. Then the minimal (DFA) accepting (L), find by converting it into minimal DFA by subset construction Algorithm.

Hence, it is a minimal DFA with 4 states.

Correct Option: B

The given regular expression is (a + b) * b (a + b). In this all string whose second last bit is ‘b’. So, the minimal NFA is

It can be described as “All string over {a, b} ending with ‘ba’ or ‘bb’. Then the minimal (DFA) accepting (L), find by converting it into minimal DFA by subset construction Algorithm.

Hence, it is a minimal DFA with 4 states.