Quiz 1: Introduction To Finite Automata

Reviewed by Editorial Team
The ProProfs editorial team is comprised of experienced subject matter experts. They've collectively created over 10,000 quizzes and lessons, serving over 100 million users. Our team includes in-house content moderators and subject matter experts, as well as a global network of rigorously trained contributors. All adhere to our comprehensive editorial guidelines, ensuring the delivery of high-quality content.
Learn about Our Editorial Process
| By Nayak23
N
Nayak23
Community Contributor
Quizzes Created: 1 | Total Attempts: 2,070
| Attempts: 2,074
SettingsSettings
Please wait...
  • 1/10 Questions

    A DFA has infinite number of states

    • True
    • False
Please wait...
Quiz 1: Introduction To Finite Automata - Quiz
About This Quiz

A finite automaton is a state machine that takes a string of symbols as input and changes its state accordingly. When a regular expression string is fed into finite automata, it changes its state for each literal. If you think you know the basics, take the quiz below. Good luck!

Quiz Preview

  • 2. 

    There are ________ tuples in finite state machine

    • 4

    • 5

    • 6

    • Unlimited

    Correct Answer
    A. 5
    Explanation
    A finite state machine is a mathematical model used to represent systems with a finite number of states and transitions between those states. In this case, the correct answer is 5 because a finite state machine can have 5 tuples, which consist of the current state, input symbol, next state, output symbol, and action. These tuples define the behavior and transitions of the finite state machine.

    Rate this question:

  • 3. 

    Number of states require to accept string ends with 10.

    • 3

    • 2

    • 1

    • Can't be represented

    Correct Answer
    A. 3
    Explanation
    The correct answer is 3 because to accept a string that ends with 10, we need to consider three possible states. The first state represents the initial state where the string has not started yet. The second state represents the state where the string has started but has not yet reached the last character. The third state represents the final state where the string has reached the last character and ends with 10. Therefore, we need three states to accept such a string.

    Rate this question:

  • 4. 

    DFA stands for?

    Correct Answer
    Deterministic finite automata
    Explanation
    DFA stands for Deterministic Finite Automata. A DFA is a type of finite automaton that recognizes a regular language. It consists of a set of states, a set of input symbols, a transition function, a start state, and a set of final states. In a DFA, for each input symbol, there is exactly one transition from each state. The term "deterministic" refers to the fact that the next state is uniquely determined by the current state and the input symbol. The term "finite" indicates that the number of states in a DFA is finite.

    Rate this question:

  • 5. 

    Give a Regular Expression for: L = {0i 1j | i is even and j is odd }

    • (00)∗0(11)∗

    • (00)∗1(11)∗

    • (00)∗10(11)∗

    • None

    Correct Answer
    A. (00)∗1(11)∗
    Explanation
    The regular expression (00)*1(11)* matches strings in the language L = {0i 1j | i is even and j is odd}.


    - (00)* matches zero or more occurrences of the string "00".
    - 1 matches the character "1".
    - (11)* matches zero or more occurrences of the string "11".

    Therefore, the regular expression (00)*1(11)* ensures that the string starts with an even number of "0"s (i.e., i is even) followed by a single "1" and ends with an odd number of "1"s (i.e., j is odd), which satisfies the given language L.

    Rate this question:

  • 6. 
    Among the 4 strings listed, which one is rejected by the DFA - ProProfs

    Among the 4 strings listed, which one is rejected by the DFA

    • Baaaab

    • Aaaaab

    • Aabb

    • Abbab

    Correct Answer
    A. Aabb
    Explanation
    The DFA rejects the string "aabb" because it does not match the pattern or language accepted by the DFA. The DFA may have specific rules or transitions that determine which strings are accepted or rejected, and "aabb" does not meet those criteria.

    Rate this question:

  • 7. 

    Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

    • The set of all strings containing the substring 00

    • The set of all strings containing at most two 0’s

    • The set of all strings containing at least two 0’s

    • The set of all strings that begin and end with either 0 or 1

    Correct Answer
    A. The set of all strings containing at least two 0’s
    Explanation
    The regular expression (0+1)*0(0+1)*0(0+1)* describes the set of all strings containing at least two 0's. This is because the expression (0+1)*0(0+1)*0(0+1)* matches any string that has at least two occurrences of the digit 0. The (0+1)* part allows for any number of occurrences of 0 or 1 before and after the first and second 0, while the two 0's in the middle ensure that there are at least two 0's in the string.

    Rate this question:

  • 8. 

    Regular expression for all strings starts with ab and ends with bba is

    • Aba*b*bba

    • Ab(ab)*bba

    • Ab(a+b)*bba

    • All of the mentioned

    Correct Answer
    A. Ab(a+b)*bba
    Explanation
    The regular expression "ab(a+b)*bba" represents all strings that start with "ab" and end with "bba". The "ab" at the beginning ensures that the string starts with "ab", followed by zero or more occurrences of either "a" or "b" (represented by "(a+b)*"). Finally, the "bba" at the end ensures that the string ends with "bba". Therefore, this regular expression covers all possible strings that satisfy the given condition.

    Rate this question:

  • 9. 
    Which of the following is  FALSE?1)  L(A) = L((11*0+0)(0 + 1)*0*1*)2)  A accepts all strings over {0, 1} of length at least 2  - ProProfs

    Which of the following is  FALSE?1)  L(A) = L((11*0+0)(0 + 1)*0*1*)2)  A accepts all strings over {0, 1} of length at least 2 

    • 1

    • 2

    • 1 and 2

    • None

    Correct Answer
    A. 2
    Explanation
    The given correct answer is 2) A accepts all strings over {0, 1} of length at least 2. This statement is false because the language accepted by A is defined as L(A) = L((11*0+0)(0 + 1)*0*1*), which means that A accepts strings that start with two 1's followed by any number of 0's or 1's, and ends with 0's followed by 1's. Therefore, A does not accept all strings over {0, 1} of length at least 2, making the statement false.

    Rate this question:

  • 10. 

    Given the language L = {ab, aa, baa}, which of the following strings are in L*? 

    • Abaabaaabaa

    • Aaaabaaaa

    • Baaaaabaaaab

    • Baaaaabaa

    Correct Answer(s)
    A. Abaabaaabaa
    A. Aaaabaaaa
    A. Baaaaabaa
    Explanation
    (You can select more than one option)

    Rate this question:

Quiz Review Timeline (Updated): Mar 19, 2023 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Mar 19, 2023
    Quiz Edited by
    ProProfs Editorial Team
  • Jan 22, 2016
    Quiz Created by
    Nayak23
Back to Top Back to top
Advertisement
×

Wait!
Here's an interesting quiz for you.

We have other quizzes matching your interest.