Quiz 3 toc

The number of states required to automate the last question i.e. {a,b}*{aba}{a,b}* using finite automata:

• 4

• 3

• 5

• 6

The machine accept the string by entering into hA or it can:

• explicitly reject x by entering into hR

• enter into an infinte loop

• explicitly reject x by entering into hR and enter into an infinte loop

• None of the mentioned

Which of the following can accept even palindrome over {a,b}

• Push down Automata

• Turing machine

• NDFA

• All of the mentioned

Which of the functions can a turing machine not perform?

• Copying a string

• Deleting a symbol

• Accepting a pal

• Inserting a symbol

If T1 and T2 are two turing machines. The composite can be represented using the expression:

• T1T2

• T1 U T2

• T1 X T2

• None of the mentioned

The class of recursively enumerable language is known as:

• Turing Class

• Recursive Languages

• Universal Languages

• RE

A language L is said to be Turing decidable if:

• recursive

• TM recognizes L

• TM accepts L

• recursive & TM recognizes L

Which of the following statements are false?

• Every recursive language is recursively enumerable

• Recursively enumerable language may not be recursive

• Recursive languages may not be recursively enumerable

• None of the mentioned

Choose the correct option:

Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are recursively enumerable.

• L1 U L2

• L2 ∩ L2

• Both L1 U L2 and L2 ∩ L2

• None of the mentioned

If L is a recursive language, L’ is:

• Recursive

• Recursively Enumerable

• Recursive and Recursively Enumerable

• None of the mentioned