Toc Quiz Questions And Answers
How much do you know about TOC? Would you like to go through these TOC quiz questions and answers that we have brought for you? In theoretical computer science and mathematics, the theory of computation is known as the branch that focuses on what problems are able to be solved on a model of computation using an algorithm and to what degree they can be solved. Let's see what you know. All the best, and have fun!
Questions and Answers
- 1.
Which of the following statements is true?i) If L is a regular language, then LR is also a regular languageii) If L is a regular language, then L2 may not be a regular languageiii) The grammar {G = ({S}, {a}, S, {S->Saaa | aS| a})} is not regulariv) The grammar {G = ({S}, {a, b}, S, {S->aS | bS| })} is not regular
- A.
I only
- B.
I and iii and iv only
- C.
Ii, iii, and iv only
- D.
Iii and iv only
Correct Answer
A. I onlyExplanation
The statement "If L is a regular language, then LR is also a regular language" is true. This means that if L is a regular language, then the language formed by reversing all the strings in L (denoted as LR) is also regular. This property holds for regular languages and can be proven using various methods such as constructing a finite automaton or using regular expressions.Rate this question:
-
- 2.
Define FOUR (w) for a finite string w, to be the string consisting of the symbols of w in positions that are multiples of four. For example, FOUR (1110011100) = 01. If L is a regular language, then { FOUR (w): w є L} must be regular.
- A.
True
- B.
False
- C.
Can't say
- D.
None of these
Correct Answer
A. TrueExplanation
The given statement is true. If L is a regular language, then { FOUR (w): w є L} must also be regular. This is because regular languages are closed under homomorphism, which means that applying a homomorphism to a regular language will result in another regular language. In this case, the homomorphism is the function FOUR, which takes a string and returns a new string consisting of only the symbols in positions that are multiples of four. Since regular languages are closed under homomorphism, the resulting language { FOUR (w): w є L} will also be regular.Rate this question:
-
- 3.
If L is a language over an alphabet, ∑ let NoPrefix(L) = {x є L: no proper prefix of x is in L}. If L is regular, then so is NoPrefix(L).
- A.
True
- B.
False
- C.
Can't Say
- D.
None of these
Correct Answer
A. TrueExplanation
If a language L is regular, it means that there exists a regular expression, finite automaton, or regular grammar that can generate L. In this case, NoPrefix(L) is a subset of L that contains all the words in L that do not have any proper prefixes that are also in L. Since L is regular, it can be generated by a regular expression, finite automaton, or regular grammar. We can modify this regular expression, finite automaton, or regular grammar to generate NoPrefix(L) instead by simply excluding any words with proper prefixes that are also in L. Therefore, NoPrefix(L) is also regular.Rate this question:
-
- 4.
Consider the language defined by the regular expression (a + b)*b+. Which of the following regular expressions also defines that language?
- A.
(a*b+) + (b*b+)
- B.
(ab + bb)* b*
- C.
(a + b + ba)*b+
- D.
Both a and c
Correct Answer
C. (a + b + ba)*b+Explanation
The correct answer is (a + b + ba)*b+. This regular expression defines the language where any combination of 'a', 'b', and 'ba' can occur any number of times, followed by one or more 'b'. This includes strings like 'b', 'ab', 'bab', 'baab', 'abab', etc. The other options do not cover all the possible combinations and repetitions of 'a', 'b', and 'ba' as specified in the given regular expression.Rate this question:
-
- 5.
Convert the following DFA into a regular expression
- A.
0*10*1 (0 U 10*10*1)*
- B.
10* (0 U 10*10*1)* 10*
- C.
(0 U 10*10*1)* 0*10*1
- D.
None of the above
Correct Answer
A. 0*10*1 (0 U 10*10*1)*Explanation
The correct answer is "0*10*1 (0 U 10*10*1)*" because it represents a regular expression that matches strings that start with zero or more 0s, followed by a 1, followed by zero or more 1s, and then repeats the pattern of zero or more 0s followed by a 1, zero or more times. This regular expression accurately represents the language accepted by the given DFA.Rate this question:
-
- 6.
Which of the set can be recognized by DFS automata
- A.
The no. 1,2,4,…………….2n,………..written in binary
- B.
The set {1, 101, 11011,1110111…}
- C.
The no. 1,2,4,……………. ,………..written in unary
![Toc Quiz Questions And Answers - Quiz]()
- D.
The set of binary strings in which the no. of 0’s is the same as the no. of 1’s
Correct Answer
A. The no. 1,2,4,…………….2n,………..written in binaryExplanation
The set of numbers 1, 2, 4, ..., 2n, ... written in binary can be recognized by a Depth First Search (DFS) automata. This is because the binary representation of these numbers follows a pattern where each number is obtained by multiplying the previous number by 2. A DFS automata can traverse through this pattern by exploring all possible paths and backtracking when necessary. Therefore, it can recognize this set of numbers.Rate this question:
-
- 7.
The pumping lemma for regular languages can be used to
- A.
Prove that a given language is regular
- B.
Prove that a given language is not regular
- C.
Prove that all CFLs have a corresponding PDA
- D.
Prove that a given CFL is inherently ambiguous
Correct Answer
B. Prove that a given language is not regularExplanation
The pumping lemma for regular languages is a tool used to prove that a given language is not regular. It states that for any regular language, there exists a pumping length such that any string in the language longer than the pumping length can be divided into five parts, where the middle three parts can be repeated any number of times. By applying the pumping lemma, if we can show that a language cannot satisfy this property, we can conclude that it is not regular. Therefore, the pumping lemma can be used to prove that a given language is not regular.Rate this question:
-
- 8.
Read the following statements1) For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state2) Regular sets are closed under infinite union3) Regular sets are closed under the prefix Which of the following is true?
- A.
1 & 3 are only correct statements
- B.
1, 2 & 3 statements are correct
- C.
1 is the only correct statement
- D.
None of the above is correct
Correct Answer
A. 1 & 3 are only correct statementsExplanation
The statement "For every NFA with an arbitrary no. of final states there is an equivalent NFA with only one final state" is true because it is possible to convert an NFA with multiple final states into an equivalent NFA with only one final state by adding a new final state and redirecting all transitions from the original final states to the new final state.
The statement "Regular sets are closed under the prefix" is also true because if a language is regular, then all its prefixes are also regular. This is because adding any finite number of symbols to the beginning of a regular language will still result in a regular language.Rate this question:
-
- 9.
The finite state machine is described by the following state diagram with A as starting state where an arc label is x/y and, x stands for 1-bit input & y stands for 2-bit output.
- A.
Output 01 whenever the input sequence contains 11
- B.
Output 10 whenever the input sequence contains 10
- C.
Output the sum of the present and previous bits of the input
- D.
None of the above
Correct Answer
C. Output the sum of the present and previous bits of the inputExplanation
The correct answer is "Output the sum of the present and previous bits of the input" because the state diagram does not have any arcs labeled with specific input sequences like "11" or "10". Instead, it has arcs labeled with "x/y" where "x" represents a 1-bit input and "y" represents a 2-bit output. This indicates that the machine should output the sum of the present and previous bits of the input, regardless of the specific input sequence.Rate this question:
-
- 10.
Which of the following statement is true?
- A.
The language { : n >= 0, n !=4} is regular
![Toc Quiz Questions And Answers - Quiz]()
- B.
The set of all real numbers is a regular language.
- C.
The language { : n = i+ jk; i, k fixed, j=0,1,2………….} is regular
![Toc Quiz Questions And Answers - Quiz]()
- D.
All of the above
Correct Answer
D. All of the aboveExplanation
All of the given statements are true.
The language {: n >= 0, n !=4} is regular because it can be represented by a regular expression or a deterministic finite automaton.
The set of all real numbers is a regular language because it can be represented by a regular expression or a deterministic finite automaton.
The language {: n = i+ jk; i, k fixed, j=0,1,2………….} is regular because it can also be represented by a regular expression or a deterministic finite automaton.
Therefore, the correct answer is "All of the above".Rate this question:
-
- 11.
Let r = 1(1+0)*, s= 11* 0 & t= 1*0 be 3 regular expression as which one of the following is true
- A.
L(s) L(r) & L(s) L (t)
![Toc Quiz Questions And Answers - Quiz]()
- B.
L(r) L(s) & L(s) L (t)
![Toc Quiz Questions And Answers - Quiz]()
- C.
L (t) L(s) & L(r) L(s)
![Toc Quiz Questions And Answers - Quiz]()
- D.
L (t) L(s) & L(s) L(r)
![Toc Quiz Questions And Answers - Quiz]()
Correct Answer
A. L(s) L(r) & L(s) L (t)Explanation
The correct answer is L(s) L(r) & L(s) L (t). This means that the language generated by regular expression s concatenated with the language generated by regular expression r is equal to the language generated by regular expression s concatenated with the language generated by regular expression t.Rate this question:
-
- 12.
Which of the following is true
- A.
A(ab)*a = a(ba)* & (P*Q*) = (P*+Q*)*
- B.
(a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)*
- C.
(a+b)*ab[(a+b)*ab(a+b)*+b*a*+b*a*] = (a+b)*
- D.
None of the above
Correct Answer
B. (a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)*Explanation
The given equation (a+b)*a(a+b)*b(a+b)* = (a+b)*ab(a+b)* states that any string consisting of a or b, followed by any number of a's and b's, followed by any number of a's and b's, followed by any number of a's and b's, is equal to any string consisting of a or b, followed by any number of a's and b's, followed by ab, followed by any number of a's and b's. This is true because both sides of the equation represent the same language, which is the set of all possible strings that can be formed using a and b.Rate this question:
-
- 13.
A finite state machine with the following states table has a single input x & single output z. If the initial state is unknown, then the shortest input sequence to reach the final state C is
- A.
01
- B.
10
- C.
110
- D.
101
Correct Answer
A. 01Explanation
The shortest input sequence to reach the final state C is "01" because the finite state machine transitions from the initial state to state C when the input sequence is "01".Rate this question:
-
- 14.
Consider the following FAs. Which of the following is true?
- A.
FA1 FA2
![Toc Quiz Questions And Answers - Quiz]()
- B.
FA2 FA1
![Toc Quiz Questions And Answers - Quiz]()
- C.
FA1 = FA2
- D.
None of the above
Correct Answer
B. FA2 FA1Explanation
The correct answer is "FA2 FA1". This means that the FA2 comes before FA1. In the context of finite automata, the order of the automata can be important in determining the behavior or properties of the system.Rate this question:
-
- 15.
The language accepted by push down automaton in which the stack is limited to 10 items is best described as
- A.
Context Free
- B.
Regular
- C.
Deterministic Context free
- D.
Recursive
Correct Answer
B. RegularExplanation
A push down automaton is a type of automaton that uses a stack to store information. In this question, the stack is limited to only 10 items. Regular languages are a type of language that can be recognized by a finite state machine, which is a simpler type of automaton compared to a push down automaton. Since the language accepted by the push down automaton in this case can be recognized by a simpler type of automaton (finite state machine), it is best described as a regular language.Rate this question:
-
- 16.
Regular expression corresponding to the following FA will be
- A.
(ab + aaa*b)*(a+ )
![Toc Quiz Questions And Answers - Quiz]()
- B.
(ab + aaa*b)*
- C.
(a + aaa*b)* (a+ )
![Toc Quiz Questions And Answers - Quiz]()
- D.
None of the above
Correct Answer
A. (ab + aaa*b)*(a+ )Explanation
The regular expression (ab + aaa*b)*(a+) corresponds to the given finite automaton (FA). This regular expression represents a language that consists of any number of occurrences of the pattern "ab" or "aaa*b" followed by one or more occurrences of "a". The asterisk (*) denotes zero or more occurrences, and the plus sign (+) denotes one or more occurrences. Therefore, this regular expression captures all possible strings that can be accepted by the given FA.Rate this question:
-
.JPG "Convert the following DFA into a regular expression")
.JPG "A finite state machine with the following states table has a single input x & single output z. If the initial state is unknown, then the shortest input sequence to reach the final state C is")
.JPG "Consider the following FAs. Which of the following is true?")
.JPG "Regular expression corresponding to the following FA will be")
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Aug 24, 2023Quiz Edited by
ProProfs Editorial Team -
Oct 26, 2013Quiz Created by
Dheerajjetha
- Aptitude Test Quizzes
- Course Test Quizzes
- Driving Test Quizzes
- English Test Quizzes
- FCAT Quizzes
- General Knowledge Quizzes
- Intelligence Test Quizzes
- Medical Test Quizzes
- Mock Test Quizzes
- Philosophy Test Quizzes
- Practice Test Quizzes
- Pretest Quizzes
- Safety Test Quizzes
- Skill Assessment Quizzes
- Spelling Test Quizzes
- Standardized Test Quizzes
Back to top