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.
For the above specified passage, which of the following is DFA for the language represented/accepeted by machine?
A DFA must have exactly one transition for every state and every input symbol, and it must accept exactly the strings that contain abb. A DFA need not be minimal: extra states are allowed as long as the language is unchanged.
Step 1 — Read the six-state drawing as a transition table:
| State | on a | on b | Accepting? |
|---|---|---|---|
| → 1 | 2 | 1 | No |
| 2 | 2 | 3 | No |
| 3 | 2 | 4 | No |
| 4 | 5 | 4 | Yes |
| 5 | 5 | 6 | Yes |
| 6 | 5 | 4 | Yes |
Step 2 — Every state has one a-move and one b-move, so it is a complete DFA.
Step 3 — States 1, 2, 3 record the progress towards abb (nothing, a, ab), and the only way to leave them is the b-edge 3 → 4, which is taken exactly when abb has just been read. States 4, 5 and 6 are all accepting and never lead back to 1, 2 or 3, so once abb has occurred every continuation is accepted. The language is therefore exactly \((a+b)^{*}abb(a+b)^{*}\).
The drawing with a loop on a, b at state 1 and an a-edge from state 1 has two a-moves from state 1, so although it describes the right language it is an NFA, not a DFA. The four-state drawing without the a-move from state 3 back to state 2 rejects ababb, because state 3 has nowhere to go on a. The drawing that starts with a b-edge 1 → 2 needs a b before the pattern and so rejects abb itself.
The six-state automaton whose states 4, 5 and 6 are all accepting, with 3 –b→ 4, 4 –a→ 5 and 6 –b→ 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 mentioned passage which of the following is correct?
Which of the following represented the minimum state DFA for the above specified passage?
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
