Test Your Knowledge on Finite Automata

Multiple Choice Questions on Automata 

Q1. Finite state machine can recognize which of the following languges:

       (A) Only context-free grammar

       (B) Only regular grammar

       (C) Any unambiguous grammar

       (D) Any grammar

Q2. The language, L is defined over Σ = {0, 1, 2, 3, 4, 5, 6, 7} has the following set of strings included in its dictionary:

L = {7, 16, 43, 61, 223, ...} 

Identify the language represented by L from the following options:

       (A) Alternate odd and even numbers

       (B) Octal representation of a number

       (C) Divisible by 7

       (D) Octal representation of a number divisible by 7.

Q3.  Which of the following statements about ε-moves (epsilon transitions) in Finite Automata is correct?

       (A) An ε-move consumes one input symbol from the alphabet

       (B) ε-moves are allowed only in DFA

       (C) ε-moves allow the automaton to change states without consuming any input symbol

       (D) An automaton with ε-move always accepts all input strings

Q4.

       (A) Regular Language

       (B) Context-Sensitive Language

       (C) Context-Free Language

       (D) Phrase-Structure Language

Q5. Consider the given finite automaton and identify the Language recognised by it:

        (A) A DFA that accepts all strings that end with "ba"

        (B) A DFA that accepts all strings that end with "a"

        (C) A DFA that accepts all strings that end with "b"

        (D) A DFA that accepts all strings that end with "ab"

Q6.  In the automaton below, s is the start state and t is only final state.

Q7.  The below transition diagram of a finite automaton accepts which of the following set of strings?

Q8.  For the given NFA which of the following is the equivalent DFA:

Q9. How many states will the DFA equivalent of NFA with n states have in the worst case?

 

        (A) n

        (B) 2n

        (C) 2ⁿ

        (D) n²

Q10. Two finite state machines are said to be equivalent if they:

 

        (A) Have the same number of edges

        (B) Have the same number of states

        (C) Recognise the same set of tokens

        (D) Have the same number of edges and states

Q11.  ‘Every NFA can be simulated by a DFA’. The statement is true/false?

Design Automata for Representing a Language

Q1.  Consider the following NFA and answer the following:

        a) Give all the strings of length three or less accepted by the automaton.

        b) Convert the automaton to a DFA.

Q2.  Consider the following ε-NFA and do the following:

      a) Compute the ε-closure of each state.

        b) Give all the strings of length three or less accepted by the automaton.

        c) Convert the automaton to a DFA.

Q3.  Constructure the Finite Automata from the following 5-tuple notation: