Explore topic-wise InterviewSolutions in .

This section includes InterviewSolutions, each offering curated multiple-choice questions to sharpen your knowledge and support exam preparation. Choose a topic below to get started.

1.

Reverse of a DFA can be formed by(a) using PDA(b) making final state as non-final(c) making final as starting state and starting state as final state(d) None of the mentionedI got this question in an interview for job.This key question is from Union, Intersection & Complement topic in division Finite Automata of Automata Theory

Answer»

Right option is (c) making final as STARTING STATE and starting state as final state

To elaborate: By making final state as starting state string starting from end will be accepted.
Discussion
2.

Reverse of (0+1)* will be(a) Phi(b) Null(c) (0+1)*(d) (0+1)The question was asked during an online interview.I would like to ask this question from Union, Intersection & Complement topic in division Finite Automata of Automata Theory

Answer»

Right ANSWER is (c) (0+1)*

To explain: There is only one STATE which is START and FINAL state of DFA so interchanging starting start and final state doesn’t change DFA.
Discussion
3.

Which of the following do we use to form an NFA from a regular expression?(a) Subset Construction Method(b) Power Set Construction Method(c) Thompson Construction Method(d) Scott Construction MethodI have been asked this question in unit test.The above asked question is from Equivalence of NFA and DFA topic in portion Finite Automata of Automata Theory

Answer»

Correct option is (C) Thompson Construction Method

For EXPLANATION I WOULD say: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input ALPHABETS.
Discussion
4.

If L1 and L2 are regular languages, which among the following is an exception?(a) L1 U L2(b) L1 – L2(c) L1 ∩ L2(d) All of the mentionedThis question was posed to me by my college director while I was bunking the class.This interesting question is from Applications of DFA topic in chapter Finite Automata of Automata Theory

Answer»

The correct option is (d) All of the mentioned

Explanation: It the closure property of Regular language which LAYS down the FOLLOWING STATEMENT:

If L1, L2 are 2- regular languages, then L1 U L2, L1 ∩ L2, L1^C, L1 – L2 are regular language.
Discussion
5.

The automaton which allows transformation to a new state without consuming any input symbols:(a) NFA(b) DFA(c) NFA-l(d) All of the mentionedI got this question in an internship interview.This interesting question is from Uses of Epsilon-Transitions topic in division Finite Automata of Automata Theory

Answer»

Correct option is (C) NFA-l

For explanation I WOULD say: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon MOVES or lambda TRANSITIONS.
Discussion
6.

If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:(a) initial state(b) transition symbol(c) accepting state(d) intermediate stateI got this question in an online interview.My question is taken from Extended Transition Function in portion Finite Automata of Automata Theory

Answer» CORRECT option is (c) accepting STATE

The explanation: r(N) is the final state and ACCEPTS the string S after the string being TRAVERSED through r(i) other states where I ϵ 01,2…(n-2).
Discussion
7.

String X is accepted by finite automata if .(a) δ*(q,x) E A(b) δ(q,x) E A(c) δ*(Q0,x) E A(d) δ(Q0,x) E AThis question was posed to me in an online interview.This is a very interesting question from Finite Automata topic in division Finite Automata of Automata Theory

Answer» RIGHT answer is (c) δ*(Q0,x) E A

Explanation: If automata starts with starting state and after finite moves if reaches to final STEP then it CALLED accepted.
Discussion
8.

The password to the admins account=”administrator”. The total number of states required to make a password-pass system using DFA would be __________(a) 14 states(b) 13 states(c) 12 states(d) A password pass system cannot be created using DFAI got this question during an interview for a job.This is a very interesting question from DFA Processing Strings topic in section Finite Automata of Automata Theory

Answer»

Right option is (a) 14 states

To ELABORATE: For a STRING of n characters with no repetitive substrings, the number of states REQUIRED to pass the string is n+1.
Discussion
9.

Which of the following belongs to the epsilon closure set of a?(a) {f1, f2, f3}(b) {a, f1, f2, f3}(c) {f1, f2}(d) none of the mentionedI got this question in examination.I need to ask this question from Mealy Machine-II in division Finite Automata of Automata Theory

Answer» CORRECT answer is (B) {a, f1, f2, f3}

Best explanation: The epsilon closure of the SET Q is the set that contains q, together with all the states which can be reached STARTING at q by following only epsilon transitions.
Discussion
10.

State true or false:Statement: Both NFA and e-NFA recognize exactly the same languages.(a) Statement: Both NFA and e-NFA recognize exactly the same languages.(b) true(c) falseI got this question by my school teacher while I was bunking the class.My enquiry is from Mealy Machine-II topic in division Finite Automata of Automata Theory

Answer» CORRECT answer is (a) Statement: Both NFA and e-NFA recognize EXACTLY the same languages.

The best explanation: e-NFA do COME up with a CONVENIENT feature but nothing new.They do not extend the class of languages that can be represented.
Discussion
11.

An e-NFA is ___________ in representation.(a) Quadruple(b) Quintuple(c) Triple(d) None of the mentionedThe question was posed to me in final exam.The origin of the question is Mealy Machine-II in portion Finite Automata of Automata Theory

Answer»

The correct option is (B) Quintuple

To ELABORATE: An e-NFA consist of 5 TUPLES: A=(Q, S, d, Q0. F)

Note: e is never a member of S.
Discussion
12.

Homomorphism of a regular set is _______(a) Universal set(b) Null set(c) Regular set(d) Non regular setThis question was posed to me by my college director while I was bunking the class.This key question is from Union, Intersection & Complement in section Finite Automata of Automata Theory

Answer»

Correct CHOICE is (C) REGULAR set

Easiest EXPLANATION: Regular set are closed under homomorphism.
Discussion
13.

If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be(a) Empty set(b) CFG(c) Decidable(d) RegularThe question was asked in an interview for internship.My doubt stems from Union, Intersection & Complement topic in portion Finite Automata of Automata Theory

Answer» CORRECT CHOICE is (d) REGULAR

Easiest EXPLANATION: Regular is closed under difference.
Discussion
14.

Languages of a automata is(a) If it is accepted by automata(b) If it halts(c) If automata touch final state in its life time(d) All language are language of automataThis question was posed to me during an internship interview.The origin of the question is Finite Automata in portion Finite Automata of Automata Theory

Answer» CORRECT option is (a) If it is ACCEPTED by automata

The explanation is: If a string accepted by automata it is called language of automata.
Discussion
15.

Which of the following will the given DFA won’t accept?(a) ε(b) 11010(c) 10001010(d) String of letter count 11I had been asked this question in an international level competition.Query is from Deterministic Finite Automata-Introduction and Definition topic in chapter Finite Automata of Automata Theory

Answer» RIGHT option is (a) ε

To explain I would SAY: As the initial state is not made an acceptance state, THUS ε will not be accepted by the given DFA. For the automata to ACCEPT ε as an entity, one should make the initial state as ALSO the final state.
Discussion
16.

Choose the correct option:(a) Statement 1 is true and Statement 2 is true(b) Statement 1 is true while Statement 2 is false(c) Statement 1 is false while Statement 2 is true(d) Statement 1 and Statement 2, both are falseI had been asked this question by my college professor while I was bunking the class.My doubt is from Moore Machine topic in division Finite Automata of Automata Theory

Answer» CORRECT ANSWER is (a) STATEMENT 1 is true and Statement 2 is true

To explain I would say: Even ε, when PASSED as an input to Moore machine produces an OUTPUT.
Discussion
17.

Which of the following is a not a part of 5-tuple finite automata?(a) Input alphabet(b) Transition function(c) Initial State(d) Output AlphabetI had been asked this question in an online quiz.This interesting question is from Finite Automata-Introduction topic in division Finite Automata of Automata Theory

Answer»

The CORRECT choice is (d) OUTPUT ALPHABET

For explanation: A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite SET of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
Discussion
18.

Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?(a) yes(b) noI have been asked this question in an interview.My enquiry is from Uses of Epsilon-Transitions in division Finite Automata of Automata Theory

Answer»

The correct option is (a) yes

Best EXPLANATION: Yes, the language is PRESERVED during the dteps of CONSTRUCTION: L(N)=L(N1)=L(N2)=L(3).
Discussion
19.

If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?(a) 64(b) 32(c) 128(d) 127The question was posed to me in class test.I'd like to ask this question from Non Deterministic Finite Automata in portion Finite Automata of Automata Theory

Answer»

The correct option is (c) 128

Explanation: The maximum NUMBER of sets for DFA CONVERTED from NFA WOULD be not greater than 2n.
Discussion
20.

Complement of a ^ nb ^ m where n >= 4 and m

Answer» RIGHT ANSWER is (d) TYPE 3

Best EXPLANATION: It is a regular expression.
Discussion
21.

Finite automata requires minimum _______ number of stacks.(a) 1(b) 0(c) 2(d) None of the mentionedThis question was posed to me in a national level competition.Origin of the question is Finite Automata in chapter Finite Automata of Automata Theory

Answer» RIGHT option is (b) 0

The BEST I can explain: Finite automata doesn’t REQUIRE any stack OPERATION .
Discussion
22.

What the following DFA accepts?(a) x is a string such that it ends with ‘101’(b) x is a string such that it ends with ‘01’(c) x is a string such that it has odd 1’s and even 0’s(d) x is a strings such that it has starting and ending character as 1I have been asked this question in homework.This interesting question is from Deterministic Finite Automata-Introduction and Definition in section Finite Automata of Automata Theory

Answer» CORRECT choice is (a) x is a STRING such that it ends with ‘101’

For EXPLANATION I would say: Strings such as {1101,101,10101} are being ACCEPTED while {1001,11001} are not. Thus, this conclusion LEADS to option a.
Discussion
23.

The minimum number of states required to recognize an octal number divisible by 3 are/is(a) 1(b) 3(c) 5(d) 7The question was posed to me in quiz.This interesting question is from Finite Automata-Introduction topic in section Finite Automata of Automata Theory

Answer»

Correct option is (B) 3

Explanation: According to the question, minimum of 3 states are required to recognize an octal number DIVISIBLE by 3.
Discussion
24.

a ^ nb ^ n where (n+m) is even .(a) Type 0(b) Type 1(c) Type 2(d) Type 3I got this question by my college professor while I was bunking the class.Question is from Union, Intersection & Complement topic in division Finite Automata of Automata Theory

Answer» RIGHT ANSWER is (d) TYPE 3

Explanation: It is a REGULAR EXPRESSION.
Discussion
25.

Which of the steps are non useful while eliminating the e-transitions for the given diagram?(a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N(b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in ECLOSE(a) to f1(c) Delete all arcs labelled as e(d) None of the mentionedI had been asked this question during an internship interview.The question is from Epsilon Closures topic in division Finite Automata of Automata Theory

Answer» CORRECT choice is (d) None of the mentioned

To elaborate: The given are the steps followed while eliminating epsilon TRANSITIONS from a NFA or converting an e-NFA to just NFA.
Discussion
26.

Which among the following can be an example of application of finite state machine(FSM)?(a) Communication Link(b) Adder(c) Stack(d) None of the mentionedI got this question by my college professor while I was bunking the class.I want to ask this question from Applications of NFA topic in section Finite Automata of Automata Theory

Answer»

The CORRECT answer is (a) Communication Link

Explanation: Idle is the state when data in form of packets is send and RETURNS if NAK is RECEIVED else WAITS for the NAK to be received.
Discussion
27.

The complement of a language will only be defined when and only when the __________ over the language is defined.(a) String(b) Word(c) Alphabet(d) GrammarThe question was posed to me in exam.I want to ask this question from Simpler Notations topic in division Finite Automata of Automata Theory

Answer»

The correct ANSWER is (c) Alphabet

To explain: It is not possible to define the COMPLEMENT of a language WITHOUT defining the input alphabets. Example: A language which does not consist of SUBSTRING ‘ab’ while the complement would be the language which does contain a substring ‘ab’.
Discussion
28.

Under which of the following operation, NFA is not closed?(a) Negation(b) Kleene(c) Concatenation(d) None of the mentionedThe question was posed to me in an internship interview.This key question is from Applications of NFA in section Finite Automata of Automata Theory

Answer» RIGHT ANSWER is (d) NONE of the mentioned

Explanation: NFA is said to be closed under the following OPERATIONS:

a) Union

b) Intersection

c) Concatenation

d) Kleene

e) Negation.
Discussion
29.

Which among the following is not an application of FSM?(a) Lexical Analyser(b) BOT(c) State charts(d) None of the mentionedThe question was posed to me in an interview.My question is from Equivalence of NFA and DFA topic in portion Finite Automata of Automata Theory

Answer»

The CORRECT answer is (d) NONE of the mentioned

Easy explanation: Finite state automation is used in Lexical Analyser, Computer BOT (used in GAMES), State CHARTS, etc.
Discussion
30.

δˆ tells us the best:(a) how the DFA S behaves on a word u(b) the state is the dumping state(c) the final state has been reached(d) Kleene operation is performed on the setThis question was posed to me during an internship interview.I would like to ask this question from The Language of DFA in portion Finite Automata of Automata Theory

Answer»

Right answer is (a) how the DFA S behaves on a WORD u

Easiest explanation: δ or the TRANSITION function describes the best, how a DFA behaves on a STRING where to TRANSIT next, which direction to take.
Discussion
31.

What does the following figure most correctly represents?(a) Final state with loop x(b) Transitional state with loop x(c) Initial state as well as final state with loop x(d) Insufficient DataI got this question in an internship interview.My question comes from Deterministic Finite Automata-Introduction and Definition in division Finite Automata of Automata Theory

Answer»

The correct choice is (c) Initial STATE as WELL as final state with loop x

The explanation is: The figure REPRESENTS the initial as well as the final state with an ITERATION of x.
Discussion
32.

Which of the following not an example Bounded Information?(a) fan switch outputs {on, off}(b) electricity meter reading(c) colour of the traffic light at the moment(d) none of the mentionedI had been asked this question by my school teacher while I was bunking the class.This intriguing question comes from Deterministic Finite Automata-Introduction and Definition in portion Finite Automata of Automata Theory

Answer»

The correct answer is (b) electricity meter reading

For EXPLANATION: BOUNDED information REFERS to one whose output is LIMITED and it cannot be said what were the RECORDED outputs previously until memorized.
Discussion
33.

The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1(a) 01,0011,010101(b) 0011,11001100(c) ε,0011,11001100(d) ε,0011,11001100This question was posed to me in an international level competition.I'm obligated to ask this question of Finite Automata-Introduction in section Finite Automata of Automata Theory

Answer»

The CORRECT CHOICE is (b) 0011,11001100

Explanation: The Kleene star of A, denoted by A*, is the SET of all strings obtained by concatenating zero or more strings from A.
Discussion
34.

The number of elements present in the e-closure(f2) in the given diagram:(a) 0(b) 1(c) 2(d) 3The question was posed to me in an online interview.My doubt stems from Mealy Machine-II in portion Finite Automata of Automata Theory

Answer»

Correct CHOICE is (c) 2

For explanation: The epsilon CLOSURE SET of f2 consist of the elements:{f2, F3}. Thus the count of the element in the closure set is 2.
Discussion
35.

The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.(a) e-closure(b) e-pack(c) Q in the tuple(d) None of the mentionedThis question was posed to me in exam.My question comes from Finite Automata with Epsilon Transition topic in division Finite Automata of Automata Theory

Answer»

The correct CHOICE is (a) e-closure

The best I can explain: The e-closure of a set of states, P, of an NFA is DEFINED as the set of states REACHABLE from any state in P following e-transitions.
Discussion
36.

According to the given table, compute the number of transitions with 1 as its symbol but not 0:(a) 4(b) 3(c) 2(d) 1I have been asked this question by my school teacher while I was bunking the class.Query is from Extended Transition Function in section Finite Automata of Automata Theory

Answer»

Correct ANSWER is (d) 1

Explanation: The TRANSITION GRAPH is made and thus the answer can be found.
Discussion
37.

It is less complex to prove the closure properties over regular languages using(a) NFA(b) DFA(c) PDA(d) Can’t be saidI got this question in quiz.I want to ask this question from Equivalence of NFA and DFA topic in chapter Finite Automata of Automata Theory

Answer»

Right option is (a) NFA

To EXPLAIN: We use the construction method to prove the validity of closure properties of REGULAR languages. THUS, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.
Discussion
38.

Number of states require to accept string ends with 10.(a) 3(b) 2(c) 1(d) can’t be represented.The question was posed to me during an interview.The question is from Finite Automata in chapter Finite Automata of Automata Theory

Answer»

The correct CHOICE is (a) 3

Best EXPLANATION: This is minimal FINITE AUTOMATA.
Discussion
39.

Let u=’1101’, v=’0001’, then uv=11010001 and vu= 00011101.Using the given information what is the identity element for the string?(a) u^-1(b) v^-1(c) u^-1v^-1(d) εI have been asked this question in a job interview.I want to ask this question from Simpler Notations topic in chapter Finite Automata of Automata Theory

Answer»

Right answer is (d) ε

To EXPLAIN: Identity relation: εw = wε = W, THUS the one satisfying the GIVEN relation will be the identity ELEMENT.
Discussion
40.

Given:(a) L= {xϵ∑= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?(b) Yes(c) NoI got this question in an online quiz.My enquiry is from DFA Processing Strings topic in division Finite Automata of Automata Theory

Answer»

Right OPTION is (b) Yes

To explain: It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus, It is not possible to build a DFA for the GIVEN LANGUAGE.
Discussion
41.

Which of the following does not belong to input alphabet if S={a, b}* for any language?(a) a(b) b(c) e(d) none of the mentionedThis question was posed to me by my college professor while I was bunking the class.I'd like to ask this question from Mealy Machine-II in chapter Finite Automata of Automata Theory

Answer»

Right ANSWER is (c) e

The explanation: The AUTOMATON may be allowed to CHANGE its STATE without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.
Discussion
42.

A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation(a) Union(b) Concatenation(c) Kleene*(d) All of the mentionedI had been asked this question in an internship interview.This intriguing question originated from Finite Automata-Introduction in chapter Finite Automata of Automata Theory

Answer»

Correct OPTION is (d) All of the mentioned

To explain: UNION, Intersection, CONCATENATION, Kleene*, Reverse are all the closure PROPERTIES of Regular Language.
Discussion
43.

Which of the given are correct?(a) Moore machine has 6-tuples(b) Mealy machine has 6-tuples(c) Both Mealy and Moore has 6-tuples(d) None of the mentionedI had been asked this question in an interview for internship.Question is taken from Mealy Machine in chapter Finite Automata of Automata Theory

Answer»

The CORRECT option is (C) Both Mealy and Moore has 6-tuples

For explanation I would SAY: Finite AUTOMATON with Output has a COMMON definition for both the categories.
Discussion
44.

Complement of regular sets are _________(a) Regular(b) CFG(c) CSG(d) REI have been asked this question in an interview for job.This key question is from Union, Intersection & Complement topic in section Finite Automata of Automata Theory

Answer»

Correct ANSWER is (a) REGULAR

Best explanation: Regular sets are CLOSED under complement OPERATION.
Discussion
45.

The e-NFArecognizable languages are not closed under :(a) Union(b) Negation(c) Kleene Closure(d) None of the mentionedThe question was posed to me in semester exam.Origin of the question is Uses of Epsilon-Transitions topic in section Finite Automata of Automata Theory

Answer»

Right CHOICE is (a,b and c)

The EXPLANATION: The languages which are recognized by an epsilon NON DETERMINISTIC automata are closed under the following operations:

a) Union

b) Intersection

c) Concatenation

d) Negation

e) Star

f) Kleene closure
Discussion
46.

For NFA with ε-moves, which among the following is correct?(a) Δ: Q X (∑ U {ε}) -> P(Q)(b) Δ: Q X (∑) -> P(Q)(c) Δ: Q X (∑*) -> P(Q)(d) All of the mentionedThe question was posed to me in an interview.This intriguing question originated from Finite Automata with Epsilon Transition topic in section Finite Automata of Automata Theory

Answer»

Right answer is (a) Δ: Q X (∑ U {ε}) -> P(Q)

Easiest explanation: Due to the presence of ε symbol, or RATHER an epsilon-move, the input ALPHABETS unites with it to form a set including ε.
Discussion
47.

e-transitions are(a) conditional(b) unconditional(c) input dependent(d) none of the mentionedI have been asked this question in unit test.Query is from Finite Automata with Epsilon Transition topic in division Finite Automata of Automata Theory

Answer»

The correct answer is (b) unconditional

For EXPLANATION I would SAY: An EPSILON move is a TRANSITION from ONE state to another that doesnt require any specific condition.
Discussion
48.

NFA, in its name has ’non-deterministic’ because of :(a) The result is undetermined(b) The choice of path is non-deterministic(c) The state to be transited next is non-deterministic(d) All of the mentionedThis question was posed to me in class test.I need to ask this question from Non Deterministic Finite Automata in section Finite Automata of Automata Theory

Answer»

Correct answer is (b) The choice of path is non-deterministic

The explanation: Non deterministic or deterministic depends UPON the definite path defined for the TRANSITION from one STATE to another or undefined(MULTIPLE PATHS).
Discussion
49.

For a DFA accepting binary numbers whose decimal equivalent is divisible by 4, what are all the possible remainders?(a) 0(b) 0,2(c) 0,2,4(d) 0,1,2,3I had been asked this question in unit test.I need to ask this question from The Language of DFA in chapter Finite Automata of Automata Theory

Answer»

The CORRECT answer is (d) 0,1,2,3

Easy explanation: All the decimal numbers on division would LEAD to only 4 REMAINDERS i.e. 0,1,2,3 (Property of Decimal division).
Discussion
50.

A DFA cannot be represented in the following format(a) Transition graph(b) Transition Table(c) C code(d) None of the mentionedThe question was posed to me during an interview.Asked question is from Deterministic Finite Automata-Introduction and Definition topic in chapter Finite Automata of Automata Theory

Answer»

Right answer is (d) None of the mentioned

To elaborate: A DFA can be represented in the FOLLOWING formats: Transition GRAPH, Transition Table, Transition tree/forest/Any programming LANGUAGE.
Discussion