Quiz 1: Introduction To Finite Automata

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.

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.

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.

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.

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.

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.

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.

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.

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.

(You can select more than one option)