Theory of Computation Quiz

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

• The set of all strings containing the substring 00.

• The set of all strings containing at most two 0’s.

• The set of all strings containing at least two 0’s.

• The set of all strings that begin and end with either 0 or 1.

Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

• Non regular language of L

• Complement of the language L

• None of the given

• All of above

Languages are proved to be regular or non regular using pumping lemma.

• True

• False

• Not always true

Which of the following will be used for text searching application-?

• NFA

• DFA

• PDA

• None of these

Which of the following strings is not generated by the following grammar? S → SaSbS ε

• aabb

• abab

• aababb

• aaabb

Which of the following statement is wrong?

• Any regular language has an equivalent context-free grammar.

• Some non-regular languages can’t be generated by any context-free grammar

• Intersection of context free language and a regular language is always context-free

• All languages can be generated by context- free grammar

For s Є (0+1)* let d(s) denote the decimal value of s(e.g.d(101)) = 5 Let L = {s Є (0+1)* d(s) mod 5=2 and d(s) mod 7 != 4} Which one of the following statements is true?

• L is recursively enumerable, but not recursive

• L is recursive, but not context-free

• L is context-free, but not regular

• L is regular

Universal Turing machine (UTM) influenced the concepts of

• computability

• interpretive implementation of programming language

• program and data is in same memory

• all are correct

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

• (L1)’ is recursive and (L2)’ is recursively enumerable

• (L1)’ is recursive and (L2)’ is not recursively enumerable

• (L1)’ and (L2)’ are recursively enumerable

• (L1)’ is recursively enumerable and (L2)’ is recursive

Recursively enumerable languages are not closed under

• Union

• homomorphism

• complementation

• concatenation