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 mentioned passage which of the following is correct?
The passage describes the language of all strings over {a, b} in which abb occurs somewhere, with any string of a's and b's allowed before and after it: \((a+b)^{*}abb(a+b)^{*}\). A nondeterministic automaton for it guesses where abb starts, reads abb, and then stays accepting whatever follows.
Step 1 — Freedom before the pattern requires a self-loop on a, b at the start state 1.
Step 2 — The pattern itself is the chain 1 –a→ 2 –b→ 3 –b→ 4.
Step 3 — Freedom after the pattern requires a self-loop on a, b at the accepting state 4.
Only the drawing with self-loops on a, b at both state 1 and accepting state 4 has all three parts.
The drawing with a loop only at state 1 accepts strings that end with abb, so a string such as abba is wrongly rejected. The drawing with a loop only at state 4 accepts strings that begin with abb, so babb is wrongly rejected. The drawing whose start state 1 is itself accepting with a loop on a, b accepts every string, including the empty string and bbb, which do not contain abb.
The automaton 1 –a→ 2 –b→ 3 –b→ 4 with self-loops on a, b at both state 1 and 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?
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
