Quiz 1: Introduction To Finite Automata
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!
- 1.
DFA stands for?
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:
- 2.
Give a Regular Expression for: L = {0i 1j | i is even and j is odd }
- A.
(00)∗0(11)∗
- B.
(00)∗1(11)∗
- C.
(00)∗10(11)∗
- D.
None
Correct Answer
B. (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:
-
- 3.
A DFA has infinite number of states
- A.
True
- B.
False
Correct Answer
B. FalseExplanation
A DFA (Deterministic Finite Automaton) has a finite number of states. This is because a DFA is a mathematical model used to describe the behavior of a finite set of states, where each state represents a unique condition or situation. The transitions between states are determined by the input symbols, and the DFA can only be in one state at a time. Therefore, the statement that a DFA has an infinite number of states is incorrect.Rate this question:
-
- 4.
Given the language L = {ab, aa, baa}, which of the following strings are in L*?
- A.
Abaabaaabaa
- B.
Aaaabaaaa
- C.
Baaaaabaaaab
- D.
Baaaaabaa
Correct Answer(s)
A. Abaabaaabaa
B. Aaaabaaaa
D. BaaaaabaaExplanation
(You can select more than one option)Rate this question:
-
- 5.
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)*?
- A.
The set of all strings containing the substring 00
- B.
The set of all strings containing at most two 0’s
- C.
The set of all strings containing at least two 0’s
- D.
The set of all strings that begin and end with either 0 or 1
Correct Answer
C. The set of all strings containing at least two 0’sExplanation
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:
-
- 6.
There are ________ tuples in finite state machine
- A.
4
- B.
5
- C.
6
- D.
Unlimited
Correct Answer
B. 5Explanation
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:
-
- 7.
Number of states require to accept string ends with 10.
- A.
3
- B.
2
- C.
1
- D.
Can't be represented
Correct Answer
A. 3Explanation
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:
-
- 8.
Regular expression for all strings starts with ab and ends with bba is
- A.
Aba*b*bba
- B.
Ab(ab)*bba
- C.
Ab(a+b)*bba
- D.
All of the mentioned
Correct Answer
C. Ab(a+b)*bbaExplanation
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.
Among the 4 strings listed, which one is rejected by the DFA
- A.
Baaaab
- B.
Aaaaab
- C.
Aabb
- D.
Abbab
Correct Answer
C. AabbExplanation
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:
-
- 10.
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
- A.
1
- B.
2
- C.
1 and 2
- D.
None
Correct Answer
B. 2Explanation
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:
-
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Mar 19, 2023Quiz Edited by
ProProfs Editorial Team -
Jan 22, 2016Quiz Created by
Nayak23