Unit 2 - Regular Languages And Finite Automata
TEST 1
- 1.
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
To accept a string that ends with "10", we need to consider the possible combinations of states that can lead to this ending. In this case, we can have three states: the initial state, a state that accepts "1", and a final state that accepts "0". The initial state transitions to the state that accepts "1", and the state that accepts "1" transitions to the final state that accepts "0". Therefore, we need three states to accept a string that ends with "10".Rate this question:
-
- 2.
Language of finite automata is.
- A.
Type 0
- B.
Type 1
- C.
Type 2
- D.
Type 3
Correct Answer
D. Type 3Explanation
The language of finite automata is Type 3. Type 3 languages are also known as regular languages, which can be recognized by finite automata. These languages can be described by regular expressions or generated by regular grammars. They are the simplest type of languages in the Chomsky hierarchy and can be represented by deterministic or non-deterministic finite automata.Rate this question:
-
- 3.
Finite automata requires minimum _______ number of stacks.
- A.
1
- B.
0
- C.
2
- D.
3
Correct Answer
B. 0Explanation
Finite automata requires minimum 0 number of stacks because it operates on a finite set of states and does not require any additional memory to keep track of its current state. It can be implemented using a simple control unit that transitions between states based on the input received, without the need for any stack data structure.Rate this question:
-
- 4.
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 "a" after "ab" allows for zero or more occurrences of "a" in between. The "(a+b)*" allows for zero or more occurrences of either "a" or "b" in between. Finally, "bba" ensures that the string ends with "bba". Therefore, this regular expression covers all possible strings that meet the given criteria.Rate this question:
-
- 5.
The basic limitation of finite automata is that
- A.
It can’t remember arbitrary large amount of information.
- B.
It sometimes recognize grammar that are not regular.
- C.
It sometimes fails to recognize regular grammar
- D.
All of the mentioned
Correct Answer
A. It can’t remember arbitrary large amount of information.Explanation
Finite automata have a limited memory capacity, which means they cannot remember an arbitrary large amount of information. This limitation is due to the fact that finite automata have a fixed number of states and can only store a finite amount of information in these states. Therefore, when faced with complex problems or inputs that require remembering a large amount of information, finite automata are unable to effectively solve or process them.Rate this question:
-
- 6.
Transition function maps.
- A.
Σ * Q -> Σ
- B.
Q * Q -> Σ
- C.
Σ * Σ -> Q
- D.
Q * Σ -> Q
Correct Answer
D. Q * Σ -> QExplanation
The transition function maps a state (Q) and an input symbol (Σ) to a new state (Q). In other words, when the automaton is in a certain state and receives a certain input symbol, the transition function determines the next state that the automaton will transition to. Therefore, the correct answer is Q * Σ -> Q, where Q represents the set of states and Σ represents the set of input symbols.Rate this question:
-
- 7.
Regular expressions that do not contain the star operator can represent only finite languages.
- A.
True
- B.
False
Correct Answer
A. TrueExplanation
Regular expressions are a way to describe patterns in strings. The star operator (*) in regular expressions allows for repetition of a character or group of characters. If a regular expression does not contain the star operator, it means that it cannot represent infinite repetition. Therefore, it can only represent a finite language, as it can only describe patterns that have a finite number of possible strings. Hence, the statement "Regular expressions that do not contain the star operator can represent only finite languages" is true.Rate this question:
-
- 8.
A language is regular if and only if
- A.
Accepted by DFA
- B.
Accepted by PDA
- C.
Accepted by LBA
- D.
Accepted by Turing machine
Correct Answer
A. Accepted by DFAExplanation
A language is considered regular if and only if it can be accepted by a Deterministic Finite Automaton (DFA). This means that there exists a DFA that can recognize and accept all the strings in the language. The DFA follows a set of predefined rules and transitions based on the current state and input symbol, ultimately leading to either an accepting or rejecting state. Therefore, if a language can be accepted by a DFA, it is regular.Rate this question:
-
- 9.
Regular expressions are closed under
- A.
Union
- B.
Intersection
- C.
Kleen star
- D.
All of the mentioned
Correct Answer
D. All of the mentionedExplanation
Regular expressions are closed under all of the mentioned operations, which means that the result of applying any of these operations to regular expressions will always produce another regular expression. This property is important in computer science and formal language theory as it allows for the manipulation and combination of regular expressions to create more complex patterns and expressions.Rate this question:
-
- 10.
Which of the following are not regular ?
- A.
String of 0's whose length is a perfect square
- B.
Set of all palindromes made up of 0's and 1's
- C.
Strings of 0's, whose length is a prime number
- D.
All of these
Correct Answer
D. All of theseExplanation
The correct answer is "All of these". None of the given options are regular languages. A regular language can be recognized by a finite automaton, but none of the given languages can be recognized by a finite automaton. The language of strings of 0's whose length is a perfect square is not regular because it requires counting and checking if the length is a perfect square. The language of palindromes made up of 0's and 1's is not regular because it requires matching characters at opposite ends of the string. The language of strings of 0's whose length is a prime number is not regular because it requires checking if the length is a prime number. Therefore, all of these languages are not regular.Rate this question:
-
- 11.
Which one do you like?
- A.
Option 1
- B.
Option 2
- C.
Option 3
- D.
Option 4
Correct Answer
A. Option 1 -
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 21, 2023Quiz Edited by
ProProfs Editorial Team -
Jan 05, 2017Quiz Created by
Jinal_parmar
Back to top