Theoretical Computer Science MCQ : Regular Language - Pumping lemma, Closure properties of regular Languages : Link3

Theoretical Computer Science MCQ & Answers

       Are you worried about the answers to Theoretical Computer Science questions :Regular Language - Pumping lemma, Closure properties of regular Languages? We have arranged the Show Answer button under the each question. Candidates can click on it to know the right option among the given alternatives. Furthermore, the applicants can check our web portal @ www.totalmcq.com to take part in more MCQ on various subject. Wish, the given information about the Theoretical Computer Science MCQ will helpful to the advance and can learn the various types of questions and answers.

Q.1. ===Consider the languages L1 = \phi and L2 = {a}. Which one of the following represents L1 L2* U L1*

A. {ε}
B. {ε, a}
C. 𝛟
D. a*

Q.2. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

A. 1, 2 and 3                                                      B. 2, 3 and 4
C. 1, 2 and 4                                                       D. 1, 3 and 4

Q.3. The set of all string over {a, b} of even length is represented by the regular expression-----

A. (ab+aa+bb+ba)*                                                              B. (a+b)*(a*+b)*
C. (a+b)*                                                             D. (ab+ba)*

Q.4. L={a^2n | n>=1} is represented by the regular expression--------

A. (aa)*
B. a*
C. aa*a
D. a*a*

Q.5. Which of the following operation can be applied on regular expressions?

A. Union                                                          B. Concatenation
C. Closure                                                              D. All of the above

Q.6. Regular expressions are used to represent which language?

A. Recursive language                                                    B. Regular language
C. Context free language                                                        D. All of the above.

Q.7. The set of all strings over ∑ = {0,1} in which all strings that beings and ends with 0 is--------

A. 0(0+1)0                                                          B. 00
C. 00(0+1)0                                          D. 00(0+1)11

Q.8. The set of all strings over ∑ = {a,b} in which all strings that starts with and ends with same letter is--------

A.[a(a+b)*b + b(a+b)*a]                                                                        B. [a(a+b)*a + b(a+b)*b]
C. a(a+b)*a                                                                    D. b(a+b)*b

Q.9. Which of the following does the given Mealy machine represents?

A. 1’s Complement                                                             B. 2’s Complement
C. 10’s Complement                                                          D. 9’s Complement

Q.10. The number of elements present in the ε-closure(A) in the given diagram.

A. 1                                                                                      B. 2
C. 3                                                                                     D. 4

Q.11. Which of the following will not be accepted by the following DFA?

A. ababaabaa                                                                      B. abbbaa
C. abbbaabb                                                                       D. abbaabbaa

Q.12. Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}

A. δ (q0, a) =q0                                                                   B. δ (F, a) =D
C. δ (F, a) =q1                                                                      D. δ (q1, a) =D

Q.13. Reverse of a DFA can be formed by----

A. using PDA
B. making final state as non-final
C. making final as starting state and starting state as final state
D. None of the above.

Q.14. The language accepted by this DFA is---

A. b*ab*ab*ab*                                                                 B. (a+b)*
C. b*a(a+b)*                                                                       D. b*ab*ab*

Q.15. The minimum state automaton equivalent to the below FSA has the following number of states----

A. 1                                                                                       B. 2
C. 3                                                                                      D. 4

Theoretical Computer Science MCQ : Regular Language - Pumping lemma, Closure properties of regular Languages : Link2

Theoretical Computer Science MCQ & Answers

       Are you worried about the answers to Theoretical Computer Science questions :Regular Language - Pumping lemma, Closure properties of regular Languages? We have arranged the Show Answer button under the each question. Candidates can click on it to know the right option among the given alternatives. Furthermore, the applicants can check our web portal @ www.totalmcq.com to take part in more MCQ on various subject. Wish, the given information about the Theoretical Computer Science MCQ will helpful to the advance and can learn the various types of questions and answers.

Q.1. The following statement is related to which theorem? "All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language."

A. Turing Machine
B. Arden’s theorem
C. Pumping Lemma
D. None of the above

Q.2. If we select a string w such that w∈L, and w=uvw Which of the following portions cannot be an empty string?

A. u                                                      B. v
C. w                                                      D. all of the above

Q.3. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|≤?

A. n                                                              B. |y|
C. |x|                                                             D. none of the above

Q.4. Fill in the blank in terms of k, where k is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______

A. k*1
B. k+1
C. k-1
D. none of the above.

Q.5. Which of the following operation can be applied on regular expressions?

A. Union                                                          B. Concatenation
C. Closure                                                              D. All of the above

Q.6. Regular expressions are used to represent which language?

A. Recursive language                                                    B. Regular language
C. Context free language                                                        D. All of the above.

Q.7. The set of all strings over ∑ = {0,1} in which all strings that beings and ends with 0 is--------

A. 0(0+1)0                                                          B. 00
C. 00(0+1)0                                          D. 00(0+1)11

Q.8. The set of all strings over ∑ = {a,b} in which all strings that starts with and ends with same letter is--------

A.[a(a+b)*b + b(a+b)*a]                                                                        B. [a(a+b)*a + b(a+b)*b]
C. a(a+b)*a                                                                    D. b(a+b)*b

Q.9. Which of the following does the given Mealy machine represents?

A. 1’s Complement                                                             B. 2’s Complement
C. 10’s Complement                                                          D. 9’s Complement

Q.10. The number of elements present in the ε-closure(A) in the given diagram.

A. 1                                                                                      B. 2
C. 3                                                                                     D. 4

Q.11. Which of the following will not be accepted by the following DFA?

A. ababaabaa                                                                      B. abbbaa
C. abbbaabb                                                                       D. abbaabbaa

Q.12. Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}

A. δ (q0, a) =q0                                                                   B. δ (F, a) =D
C. δ (F, a) =q1                                                                      D. δ (q1, a) =D

Q.13. Reverse of a DFA can be formed by----

A. using PDA
B. making final state as non-final
C. making final as starting state and starting state as final state
D. None of the above.

Q.14. The language accepted by this DFA is---

A. b*ab*ab*ab*                                                                 B. (a+b)*
C. b*a(a+b)*                                                                       D. b*ab*ab*

Q.15. The minimum state automaton equivalent to the below FSA has the following number of states----

A. 1                                                                                       B. 2
C. 3                                                                                      D. 4

Theoretical Computer Science MCQ : Regular Language - Definition, Equivalence of FA and RE : Link1

Theoretical Computer Science MCQ & Answers

       Are you worried about the answers to Theoretical Computer Science questions :Regular Language - Definition, Equivalence of FA and RE? We have arranged the Show Answer button under the each question. Candidates can click on it to know the right option among the given alternatives. Furthermore, the applicants can check our web portal @ www.totalmcq.com to take part in more MCQ on various subject. Wish, the given information about the Theoretical Computer Science MCQ will helpful to the advance and can learn the various types of questions and answers.

Q.1. Consider the languages L1 = 𝛟 and L2 = {a}. Which one of the following represents L1 L2* U L1*

A. {ε}
B. {ε, a}
C. 𝛟
D. a*

Q.2. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa

A. 1, 2 and 3                                                      B. 2, 3 and 4
C. 1, 2 and 4                                                       D. 1, 3 and 4

Q.3. The set of all string over {a, b} of even length is represented by the regular expression-----

A. (ab+aa+bb+ba)*                                                              B. (a+b)*(a*+b)*
C. (a+b)*                                                             D. (ab+ba)*

Q.4. L={a^2n | n>=1} is represented by the regular expression--------

A. (aa)*
B. a*
C. aa*a
D. a*a*

Q.5. Which of the following operation can be applied on regular expressions?

A. Union                                                          B. Concatenation
C. Closure                                                              D. All of the above

Q.6. Regular expressions are used to represent which language?

A. Recursive language                                                    B. Regular language
C. Context free language                                                        D. All of the above.

Q.7. The set of all strings over ∑ = {0,1} in which all strings that beings and ends with 0 is--------

A. 0(0+1)0                                                          B. 00
C. 00(0+1)0                                          D. 00(0+1)11

Q.8. The set of all strings over ∑ = {a,b} in which all strings that starts with and ends with same letter is--------

A.[a(a+b)*b + b(a+b)*a]                                                                        B. [a(a+b)*a + b(a+b)*b]
C. a(a+b)*a                                                                    D. b(a+b)*b

Q.9.Regular expressions are used to represent which language?

A. Recursive language                                                              B. Context free language
C. Regular language                                                          D. All of the above.

Q.10. Which of the following statement is true?

A. Every language that is defined by regular expression can also be defined by finite automata                                                                                      B. Every language defined by finite automata can also be defined by regular expression
C. We can convert regular expressions into finite automata                                                                                     D. All of the above

Q.11. Which one of the following regular expression matches any string containing zero or one p?

A. p*                                                                      B. p+
C. p?                                                                       D. p#

Q.12. Regular expression given NFA is-------

A. 01* + 1                                                                   B. 01 + 1
C. 0 + 1                                                                      D. 01 + 1*

Q.13. A language is regular if and only if-------

A. accepted by DFA
B. accepted by PDA
C. accepted by Turing machine
D. accepted by LBA

Q.14. Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then---------

A. L1=L2
C. L1 U L2 = .*                                            D. L1=L2

Q.15. Regular expression are----

A.Type 0 language                                                           B. Type 1 language
C. Type 2 language                                                            D. Type 3 language

Theoretical Computer Science MCQ : Finite Automata - conversion of dfa to nfa, Minimization of DFA : Link5

Theoretical Computer Science MCQ & Answers

       Are you worried about the answers to Theoretical Computer Science questions :Finite Automata - conversion of dfa to nfa, Minimization of DFA? We have arranged the Show Answer button under the each question. Candidates can click on it to know the right option among the given alternatives. Furthermore, the applicants can check our web portal @ www.totalmcq.com to take part in more MCQ on various subject. Wish, the given information about the Theoretical Computer Science MCQ will helpful to the advance and can learn the various types of questions and answers.

Q.1. Can a DFA recognize a palindrome number?

A. Yes
B. No
C. Yes, with input alphabet as ∑*
D. Can’t be determined

Q.2. Two finite state machines are said to be equivalent if they-----

A. Have the same number of edges                                                      B. Have the same number of states
C. Recognize the same set of tokens                                                      D. Have the same number of states and edges

Q.3. Myhill-Nerode Theorem is used for-----

A. Minimization of DFA                                                              B. Conversion of NFA
C. Conversion of DFA                                                             D. Maximization of NFA

Q.4. Number of states in the minimized DFA of the following DFA will be------

A. 1
B. 2
C. 3
D. 4

Q.5. What is thr language of the following DFA?

A. {w | w contains atleast three 0's}                                                          B. {w | w contains number of 0 as a multiple of 3 and number of 1 as a multiple of 2}
C. {w | w contains atleast three 0's and two 1's}                                                              D. {w | w contains atleast three 0's and even number of 1's}

Q.6. Which one of the following is FALSE?

A. There is unique minimal DFA for every regular language                                                    B. Every NFA can be converted to an equivalent PDA.
C. Complement of every context-free language is recursive.                                                        D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Q.7. The finite automata accept the following language------

A. context free language                                                          B. regular language
C. context sensitive language                                          D. all of the above.

Q.8. Which of the following belongs to the epsilon closure set of a?

A. {f1, f2, f3}                                                                        B. {f1, f2}
C. {a, f1, f2, f3}                                                                    D. {a, f1, f2}

Q.9. Which of the following does the given Mealy machine represents?

A. 1’s Complement                                                             B. 2’s Complement
C. 10’s Complement                                                          D. 9’s Complement

Q.10. The number of elements present in the ε-closure(A) in the given diagram.

A. 1                                                                                      B. 2
C. 3                                                                                     D. 4

Q.11. Which of the following will not be accepted by the following DFA?

A. ababaabaa                                                                      B. abbbaa
C. abbbaabb                                                                       D. abbaabbaa

Q.12. Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}

A. δ (q0, a) =q0                                                                   B. δ (F, a) =D
C. δ (F, a) =q1                                                                      D. δ (q1, a) =D

Q.13. Reverse of a DFA can be formed by----

A. using PDA
B. making final state as non-final
C. making final as starting state and starting state as final state
D. None of the above.

Q.14. The language accepted by this DFA is---

A. b*ab*ab*ab*                                                                 B. (a+b)*
C. b*a(a+b)*                                                                       D. b*ab*ab*

Q.15. The minimum state automaton equivalent to the below FSA has the following number of states----

A. 1                                                                                       B. 2
C. 3                                                                                      D. 4

Theoretical Computer Science MCQ : Finite Automata - FA with output, Minimization of DFA, Moore to Mealy machine, Mealy to Moore Machine : Link4

Theoretical Computer Science MCQ & Answers

       Are you worried about the answers to Theoretical Computer Science questions :Finite Automata - FA with output, Minimization of DFA, Moore to Mealy machine, Mealy to Moore Machine? We have arranged the Show Answer button under the each question. Candidates can click on it to know the right option among the given alternatives. Furthermore, the applicants can check our web portal @ www.totalmcq.com to take part in more MCQ on various subject. Wish, the given information about the Theoretical Computer Science MCQ will helpful to the advance and can learn the various types of questions and answers.

Q.1. Choose the correct statements.

A. Any given Mealy machine has an equivalent Moore machine.
B. Any given Moore machine has an equivalent Mealy machine.
C. Moore and Mealy machines are FSM's with output capability.
D. All of the above

Q.2. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least----

A. N^2                                                      B. 2N
C. 2^N                                                      D. N!

Q.3. The relation between NFA-accepted languages and DFA accepted languages is-----

A. >                                                              B. <
C. =                                                             D. <=

Q.4. Which one is a FALSE statement?

A. There exists a unique DFA for every regular language
B. NFA can always are converted to a PDA
C. Complement of CFL is always recursive
D. Every NDFA can be converted to a DFA

Q.5. The reorganizing capability of NDFA and DFA----

A. May be different                                                          B. Must be different
C. Must be same                                                              D. None of the above

Q.6. Grammars that can be translated to DFAs-----

A. Left linear grammar                                                    B. Right linear grammar
C. Generic grammar                                                        D. All of the above.

Q.7. A language is regular if and only if it is accepted by finite automata.

A. statement is true                                                          B. statement is false
C. Statement is partially true                                          D. None of the above.

Q.8. Which of the following belongs to the epsilon closure set of a?

A. {f1, f2, f3}                                                                        B. {f1, f2}
C. {a, f1, f2, f3}                                                                    D. {a, f1, f2}

Q.9. Which of the following does the given Mealy machine represents?

A. 1’s Complement                                                             B. 2’s Complement
C. 10’s Complement                                                          D. 9’s Complement

Q.10. The number of elements present in the ε-closure(A) in the given diagram.

A. 1                                                                                      B. 2
C. 3                                                                                     D. 4

Q.11. Which of the following will not be accepted by the following DFA?

A. ababaabaa                                                                      B. abbbaa
C. abbbaabb                                                                       D. abbaabbaa

Q.12. Which among the following is the missing transition in the given DFA?
L= {xϵ∑= {a, b} | x starts with a and ends with b}

A. δ (q0, a) =q0                                                                   B. δ (F, a) =D
C. δ (F, a) =q1                                                                      D. δ (q1, a) =D

Q.13. Reverse of a DFA can be formed by----

A. using PDA
B. making final state as non-final
C. making final as starting state and starting state as final state
D. None of the above.

Q.14. The language accepted by this DFA is---

A. b*ab*ab*ab*                                                                 B. (a+b)*
C. b*a(a+b)*                                                                       D. b*ab*ab*

Q.15. The minimum state automaton equivalent to the below FSA has the following number of states----

A. 1                                                                                       B. 2
C. 3                                                                                      D. 4