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 at least two 0’s

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 that begin and end with either 0 or 1

Quiz 1: Introduction To Finite Automata

Approved & Edited by ProProfs Editorial Team

The editorial team at ProProfs Quizzes consists of a select group of subject experts, trivia writers, and quiz masters who have authored over 10,000 quizzes taken by more than 100 million users. This team includes our in-house seasoned quiz moderators and subject matter experts. Our editorial experts, spread across the world, are rigorously trained using our comprehensive guidelines to ensure that you receive the highest quality quizzes.

Learn about Our Editorial Process

| By Nayak23

Nayak23

Community Contributor

Quizzes Created: 1 | Total Attempts: 1,747

Questions: 10 | Attempts: 1,749 | Updated: Mar 19, 2023

Questions

Settings

Create your own 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!

Questions and Answers

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:

1
4 0
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. False

Explanation
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. Baaaaabaa

Explanation
(You can select more than one option)

Rate this question:

2
0
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’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:

1
0
6.

There are ________ tuples in finite state machine
- A.
  
  4
- B.
  
  5
- C.
  
  6
- D.
  
  Unlimited
Correct Answer
B. 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:
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. 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:

0
1
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)*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.

Among the 4 strings listed, which one is rejected by the DFA
- A.
  
  Baaaab
- B.
  
  Aaaaab
- C.
  
  Aabb
- D.
  
  Abbab
Correct Answer
C. 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:
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. 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:

Quiz 1: Introduction To Finite Automata

DFA stands for?

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

A DFA has infinite number of states

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

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)*?

There are ________ tuples in finite state machine

Number of states require to accept string ends with 10.

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

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

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

Quiz 1: Introduction To Finite Automata

DFA stands for?

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

A DFA has infinite number of states

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

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)*?

There are ________ tuples in finite state machine

Number of states require to accept string ends with 10.

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

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

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

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)*?

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