CS402 Final Term Solved MCQs Updated by Junaid

1. If Σ = {aa, bb} , then Σ* will not contain

 aaabbb

•  aabbbb
•  aabbaa
•  bbaabbbb

2. “One language can have _________ TG‟s”.

•  Only one
•  Only two

 More than one

•  Only three

3. According to 1st part of the Kleene‟s theorem, If a language can be accepted by an FA then it can be accepted by a ________ as well.

•  FA
•  CFG
•  GTG
•  TG

4. Even-palindrome is a _______ language.

 Non-regular

•  Regular
•  Regular but infinite
•  Regular but finite

5. If L is a regular language then, Lc is also a _____ language.

•  Non-regular
•  Regular but finite
•  None of the given

6. Pumping lemma is generally used to prove that:

•  A given language is infinite

 A given language is not regular

•  Whether two given regular expressions of a regular language are equivalent or not

7. the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will _________ word/words.

•  accept all

 accept no (Page 85)

•  accept some
•  reject no

8. In CFG, the symbols that can’t be replaced by anything are called________.

 Terminal (Page 87)

•  Non-Terminal
•  Production
•  All of given

Q9. Which of the following is a regular language?

 String of odd number of zeroes

•  Set of all palindromes made up of 0‟s and 1‟s
•  String of 0‟s whose length is a prime number
•  All of these

10. Which of the following pairs of regular expressions are equivalent?

•  1(001)* and (10)*10

 x(xx)* and (x)*x

•  X  and X*
•  X  and X* X 

11. An alphabet of Σ is valid if

•  No letter of Σ appears in middle of any other letter
•  No letter of Σ appears at end of any other letter

 No letter of Σ appears at start of any other letter

•  No letter of Σ appears at end or middle of any other letter

12. Which of the following statement is true

•  The length of the output string is greater than length of input string in moore machine.
•  The length of the output string is greater than length of input string in mealy machine.
•  The length of the output string is equal to length of input string in moore machine.
•  The length of the output string is less than length of input string in mealy machine.

13. If a CFG has only productions of the form nonterminal → string of two nonterminals or nonterminal → one terminal then the CFG is said to be in ________

 Chomsky Normal Form

•  Ambiguous Form
•  Left Aligned Form
•  Right Aligned Form

14. We can also represent an FA using different states e.g Accept state; Reject state, Read state etc. The ________ state behaves as final state of an FA

 Accept (Page 105)

•  Pop
•  Push
•  Reject

15. where the input string is placed before it is run, is called _______

•  Date tape

 Input Tape (Page 105)

•  Output Tape