CS402 Final Term Solved MCQs Set 3 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