Deterministic Finite Automata MCQ Quiz - Objective Question with Answer for Deterministic Finite Automata - Download Free PDF

The correct answer is: Option 1

Key Points

To detect “abb”, we need at least 4 states:

1. q0 — Start state
2. q1 — After seeing 'a'
3. q2 — After seeing 'ab'
4. q3 — After seeing 'abb' → Accepting

We also need a dead state to trap wrong transitions. So the **minimum** DFA needs at least 5 states.

Option 1: This DFA uses 5 states correctly and has transitions:

• q1 → q2 (on a)
• q2 → q3 (on b)
• q3 → q4 (on b) → final
• Final state loops on a, b

Option 2: Incorrect transitions. Accepts some but not all “abb” variants. Incorrect

Option 3: Uses 6 states, which is not optimal/minimal. Incorrect

The correct answer is : option 3

Important Points

Question Objective:

We are asked to identify the grammar that correctly represents the language accepted by the machine. From the comprehension, the machine:

• Accepts all strings over Σ = {a, b}
• Strings can start and end with any combination
• Must contain the substring "abb"

Desired Grammar Structure:

We can divide the string into 3 parts to construct the grammar:

• Prefix: Any combination of 'a' and 'b' — this can be represented using recursion (A → aA | bA | ε)
• Middle: The fixed substring 'abb'
• Suffix: Again, any combination of 'a' and 'b' — again can be represented by A

Thus, an ideal grammar looks like:

S → AabbA  
A → aA | bA | ε

Option-wise Evaluation:

✅ Option 3:

S → AabbA
A → aA | bA | ε

• This grammar allows any string with 'abb' in the middle
• A before and after 'abb' ensures prefix and suffix can be anything

✅ Correct – matches the requirement precisely

❌ Option 1:

S → AabbB  
A → aA | ε  
B → bB | ε

• Introduces a separate non-terminal B after 'abb' which is not necessary
• Creates a possibility that "abb" may not be present if A and B generate empty string

Incorrect – structure deviates from strict placement of 'abb'

❌ Option 2:

S → abbA  
A → aA | ε | bA

• Prefix flexibility is missing
• Only strings starting with "abb" will be accepted

Incorrect – does not accept strings with prefix before "abb"

❌ Option 4:

S → Aabb  
A → aA | bA | ε

• No suffix A after "abb"
• Only strings ending in "abb" are accepted

Incorrect – fails to allow suffix characters after "abb"

Final Answer: Correct Option: Option 3

This grammar ensures that "abb" is included in the middle of the string and is surrounded by any number of valid symbols from Σ = {a, b}.

The correct answer is : option 3

Key Points

Comprehension Recap: The DFA must recognize strings over Σ = {a, b} that satisfy the following:

• They may start and end with any combination of 'a' and 'b'.
• The string must contain the substring 'abb' anywhere within it.

Goal: We want a DFA that detects the presence of 'abb' anywhere, and allows characters before and after it.

Basic Structure of DFA to Accept 'abb':

• q1: Start state, accepts any number of a or b.
• q2: Transition on a from q1 (start of "abb").
• q3: Transition on b from q2 (second symbol).
• q4: Transition on b from q3 – string "abb" confirmed. This is a final state.
• q4 loops on both a and b to accept trailing characters.

Option-Wise Analysis:

✅ Option 3 (Correct):

• q1 loops on a and b – allows any prefix.
• q1 --a--> q2
• q2 --b--> q3
• q3 --b--> q4 (Final State)
• q4 loops on a and b – accepts suffix after "abb".

✅ This matches the behavior expected: accepts all strings containing "abb" regardless of their prefix or suffix.

 Option 1:

• Correct prefix handling (q1 loops on a, b).
• Transitions toward detecting "abb" are correct.
• However, q4 lacks a loop on a or b.

❌ This DFA accepts only strings ending at 'abb', and fails if more characters follow.

Option 2:

• q1 does NOT loop on a or b.
• This means only strings starting with a are accepted.
• Violates the rule that string can start with any symbol.

❌ Fails to meet the start flexibility requirement.

Option 4:

• Transitions are not consistent with detecting "abb".
• q3 returns back to q1 on b, preventing reaching a final state on "abb".

❌ Cannot reach accepting state on any valid 'abb' sequence.

Final Answer: Option 3

This DFA fulfills the language requirements: accepts any string containing 'abb', with any combination of 'a' and 'b' before or after it.

The correct answer is : option 4

Comprehension Recap: The machine accepts all strings over Σ = {a, b} that contain the substring "abb", and can start and end with any combination of 'a' and 'b'.

Key Points

• A regular expression defines a language using a pattern over an alphabet (here, Σ = {a, b}).
• We are looking for a regular expression that:
  • Allows any combination of a and b before abb
  • Must contain abb somewhere in the string
  • Allows any combination of a and b after abb
• In regular expression terms, this translates to: (a + b)* abb (a + b)*

Option Analysis:

Option 1: (a + b)* aab

• This accepts all strings that end with aab.
• But it does not ensure the occurrence of 'abb' — hence, incorrect.
• ❌ Rejected

Option 2: aba(a + b)*

• Matches strings that start with aba and are followed by any characters.
• But abb is not mandatory in this structure.
• ❌ Rejected

Option 3: b(a + b)* b(a + b)* a(a + b)*

• Complicated structure, but does not guarantee the abb sequence.
• More importantly, it's disorganized and doesn't represent the core substring abb.
• ❌ Rejected

Option 4: (a + b)* abb (a + b)*

• This is the canonical regular expression for strings that:
  • Can have any characters before abb
  • Must contain abb
  • Can have any characters after it
• This is a classic regular expression format for "string containing a pattern".
• ✅ Correct Answer

 Final Answer: Option 4 — (a + b)* abb (a + b)*

Explanation: This expression ensures the presence of the required substring abb while allowing flexibility for the string to have any content before or after it, aligning with the machine's definition in the passage.

The correct answer is :option 3

Key Points

Comprehension Summary: The DFA should accept all strings over Σ = {a, b} that:

• Start and end with any combination of 'a' and 'b'
• Must contain the substring 'abb'

Concept:

• The DFA must identify the occurrence of the substring abb in the input string.
• After recognizing abb, it can accept any combination of 'a' and 'b' till the end.

Option 1:

• Only has 4 states and doesn’t seem to process the abb sequence correctly.
• No transitions explicitly validating abb.
• ❌ Incorrect DFA

Option 2:

• Starts with 'b' transitions from q1 and q2, which doesn’t help track abb.
• States don't represent memory of 'a' followed by two 'b's.
• ❌ Incorrect DFA

Option 3 (✅ Correct Answer):

• This DFA uses a sequence of 6 states to track each character of the required substring:
• q1 → q2 → q3 → q4 → q5 → q6 represents matching a → b → b
• Final state q6 ensures that the substring abb occurred.
• Transitions allow acceptance of any characters before and after the match.
• ✅ Correct DFA — accepts all strings containing 'abb'

Option 4:

• Structure is similar to option 3 but ends prematurely at state 6.
• There’s ambiguity on whether abb is fully validated with proper state transitions.
• ❌ Incomplete DFA

Final Answer: Option 3

Given language is:  L = {w₁aw₂ | w₁, w₂ ϵ {a, b}*, |w₁| = 2, |w₂| ≥ 3}

Regular expression: (a+b) (a+b) a (a+b) (a+b) (a+b)(a+b)^*

Minimum length string that is possible = (a+b) (a+b) a (a+b) (a+b) (a+b)

This string has minimum length 6. For these 7 states are needed and one trap state. So, total 8 states are needed.

DFA for given language is

Consider DFA M,

It is accepting all the string that ends with a.

Language for DFA M L(M) = {a, aa, ba, aaa, aba, …}

Regular expression = (a + b )*a

DFA N is accepting all the languages ending with b.

Language for DFA N L (n) = {b, ab, bb, aab, abb, bbb,…….}

Regular expression = (a + b)*b

Intersection of both these languages L (M) ꓵ L(N) = { } = Ø i.e. empty language

For this, we just need 1 state with all transitions to itself and no final state.

Concept:

First convert the given regular expression into an NFA and then find out the DFA from NFA.

Explanation: 

Regular expression is (a + b) * b (a + b)

NFA for this expression is given here as:

Diagram: NFA

NFA Table:

DFA Table from the above NFA

Diagram: DFA

This DFA can’t be minimized further. So, for the given regular expression minimum number of states in the DFA is 4.

Concept:

Finite state automata is a machine that can be used to solve computer programs and other sequential logics and have finite number of states at a given time. There are 6 tuples in a finite state machine.

Explanation:

Two finite state machines are said to be equivalent if they recognize the same set of tokens.

Consider two automata M₁ and M₂, these are called equivalent for an input sequence if they produce the same output result.

Example:

Regular expression: baa*b

NFA: M₁

Number of states in NFA: 4

DFA: M₂

Number of states in DFA: 5

Above two finite automata are having different number of states and edges, but they are equivalent.

Data

Language L = { aⁿ b^2m | n, m ≥ 1 }

Concept

It is easier to find the minimized DFA if we find the NFA first.

NFA of the given language.

Converting this NFA into minimized DFA

Transition table

Hence, number of states in DFA for the language L = { aⁿ b^2m | n, m ≥ 1 } is 5.

Binary strings not ending in 101 is a set that is complement to binary strings ending in 101.

Since, regular languages are closed under complement, we can first design a DFA that accept strings that surely end in 101.

For finding the complement of this DFA, we simple change the non-final states to final and final state to non-final keeping the initial state as it is.

Given regular expression: (0 + 1)*(0 + 1)(0 + 1)*

In this, there is atleast one appearance of (0 + 1).

It generates strings of type {0, 1, 00, 01, 10, 11, 000, 001, 011, ……. }

DFA for the given expression is:

Number of states in minimum sized DFA for this regular expression = 2

Number of states in DFAs accepting L and L̅ is always equal.

DFA accepting (0+1) * 0011 (0+1)* is:

Hence DFA accepting L̅ will be

It has 5 states.

Concept:

Number of a’s in x: divisible by 2 = {0, 2, 4, 6, 8, 10, 12, 14, 16…}

Number of a’s in x: divisible by 3 = {0, 3, 6, 9, 12, 15, 18, 21…}

Now the number of a’s in x: divisible by 2 and not by 3 will include elements like {2, 4, 8, 10, 14, 16…}

Therefore, DFA for such a language where the number of a’s in x is divisible by 2 but not divisible by 3 will be

• Starting state 0
• Final states 2 and 4
• Note that 0 is not a final stat here only because we have to exclude numbers divisible by 6.

Therefore the number of states in DFA is 6.

Total number of bijective from A → A where A = {1,2 3, 4, 5} is 5! = 120.

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements.