Read the following and answer the questions that follow. A machine is represented by states Q, input alphabet Σ, transition function δ. Initial state q0 and final state F. The machine accepts all the strings over Σ = {a, b}, which start and ended with any combination of all alphabet and abb works /lies as substring in all the strings to be accepted.
Which of the following represented the minimum state DFA for the above specified passage?
The machine accepts every string over {a, b} that contains abb as a substring, i.e. the language \((a+b)^{*}abb(a+b)^{*}\). A DFA for a substring pattern of length k needs k + 1 states: one for each length of the longest prefix of the pattern matched so far, the last one being an absorbing accepting state.
Step 1 — Track how much of abb has been matched: nothing (state 1), a (state 2), ab (state 3), abb found (state 4).
Step 2 — Fill every transition so the automaton is complete and deterministic:
| State | on a | on b | Meaning |
|---|---|---|---|
| → 1 (start) | 2 | 1 | no useful prefix seen |
| 2 | 2 | 3 | last symbol read is a |
| 3 | 2 | 4 | last two symbols read are ab |
| 4 (final) | 4 | 4 | abb has already occurred |
Step 3 — Minimality: the four states are pairwise distinguishable (from 1, 2, 3 the shortest suffixes leading to acceptance are abb, bb and b respectively, and 4 accepts the empty suffix), so no smaller DFA exists and the minimum DFA has exactly 4 states.
Step 4 — Compare with the drawings. The four-state chain with a self-loop on b at state 1, a self-loop on a at state 2, a pair of arcs between states 2 and 3, the b-edge from 3 to 4 and a self-loop on a, b at the accepting state 4 is the only drawing with this shape. The labels on the two arcs between states 2 and 3 are drawn interchanged; read as 2 –b→ 3 and 3 –a→ 2 it is exactly the table above.
The five-state drawing has two accepting states and a self-loop on a together with an a-edge out of state 1, so it is neither minimal nor deterministic. The six-state drawing has no b-move from state 1 and two a-moves from state 6, so it is neither minimal nor a DFA. The drawing with a self-loop on a, b at state 1 plus an a-edge 1 → 2 is an NFA, not a DFA.
The four-state automaton with a self-loop on b at state 1, a self-loop on a at state 2, arcs between states 2 and 3, and a self-loop on a, b at accepting state 4 option is correct.
Similar Questions
There are exactly __________ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.
The transition function for the language \(L = \{w \mid n_{a}(w)\) and \(n_{b}(w)\) are both odd\(\}\) is given by :
\(\delta(q_{0}, a) = q_{1}\) ; \(\delta(q_{0}, b) = q_{2}\)
\(\delta(q_{1}, a) = q_{0}\) ; \(\delta(q_{1}, b) = q_{3}\)
\(\delta(q_{2}, a) = q_{3}\) ; \(\delta(q_{2}, b) = q_{0}\)
\(\delta(q_{3}, a) = q_{2}\) ; \(\delta(q_{3}, b) = q_{1}\)
The initial and final states of the automata are :
Minimal deterministic finite automaton for the language \(L = \{0^{n} \mid n \geq 0, n \neq 4\}\) will have :
For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
For the above mentioned passage which of the following is correct?
Which of the following languages can be recognized by neither Non-Deterministic Finite Automata (NFA) nor Deterministic Finite Automata (DFA) ?
(A) L1 = {w ∈ {0, 1}* | the length of w is even}
(B) L2 = {w ∈ {0, 1}* | the length of w is odd}
(C) L3 = {w ∈ {0, 1}* | all 0′s come before all 1′s in w}
(D) L4 = {w ∈ {0, 1}* | w contains an equal number of 0′s and 1′s}
(E) L5 = {w ∈ {0, 1}* | all 1′s come before all 0′s in w}
Choose the correct answer from the options given below :
Which of the following Finite Automata, recognizes the language L={a,b}* ?
A. M=({q0}, {a,b}, δ, q0, {q0}) where, δ is
a b q0 {q0} {q0} B. M=({q0,q1}, {a,b}, δ, q0, {q0,q1}) where, δ is
a b q0 {q0,q1} {q0,q1} q1 {q1} {q1} C. M=({q0,q1}, {a,b}, δ, q0, {q0,q1}) where, δ is
a b q0 {q0,q1} {q0} q1 - {q1} D. M=({q0,q1,q2 }, {a,b}, δ, q0, {q0}) where, δ is
a b q0 {q0} {q0} q1 {q2} - q2 {q0} {q2} What is the minimum and maximum number of initial, dead, unreachable and final states in a valid ‘n’ state finite automaton, where the language accepted is not ‘φ’?
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M, whose transition table is given below (start state a; final states c, d and e).
State 0 1 a b c b a d c e f d e f e e f f f f Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes.
Important Questions from Finite Automata
Consider the DFA given below
Which of the regular expressions given below represents the above DFA ?- Let $M$ be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.
Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ? Consider the following deterministic finite automaton (DFA) defined over the alphabet, Σ = {𝑎, 𝑏}. Identify which of the following language(s) is/are accepted by the given DFA.
Consider a finite state machine (FSM) with one input 𝑋 and one output 𝑓, represented by the given state transition table. The minimum number of states required to realize this FSM is ________. (Answer in integer)
Present state Next state Output f X = 0 X = 1 X = 0 X = 1 A F B 0 0 B D C 0 0 C F E 0 0 D G A 1 0 E D C 0 0 F F B 1 1 G H 0 0 1 H G A 1 0 Consider the following DFA that generates set of strings over $\Sigma=\{a, b, c\}$
Now identify that which of the followings is the best description of the language for the above DFA
