49) If a language is denoted by a regular expression L = ( x )* (x | y x ) , then which of the following is not a legal string within L ?

xyx

x y x y x

Answer is:

x y x y x

Theory of Computation MCQ with Answers

For more MCQ's Click Here

50) If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called

decidable

undecidable

interpretive

non-deterministic

Answer is:

decidable

51) The defining language for developing a formalism in which language definitions can be stated, is called

syntactic meta language

decidable language

intermediate language

high level language

Answer is:

syntactic meta language

52) If e1and e2 are the regular expressions denoting the languages L1and L2 respectively, then which of the following is wrong ?

(e1) | (e2) is a regular expression denoting L1∪ L2

(e1) .(e2) is a regular expression denoting L1.L2

φis not a regular expression

{ex} is a regular expression denoting L1*

Answer is:

φis not a regular expression

53) Context-free grammar can be recognized by

finite state automation

2-way linear bounded automata

push down automata

both 1) 2-way linear bounded automata and 2) push down automata

Answer is:

both 1) 2-way linear bounded automata and 2) push down automata

Theory of Computation MCQ with Answers

For more MCQ's Click Here

49) If a language is denoted by a regular expression L = ( x )* (x | y x ) , then which of the following is not a legal string within L ?

x y x y x

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

50) If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called

decidable

51) The defining language for developing a formalism in which language definitions can be stated, is called

syntactic meta language

52) If e1and e2 are the regular expressions denoting the languages L1and L2 respectively, then which of the following is wrong ?

φis not a regular expression

53) Context-free grammar can be recognized by

both 1) 2-way linear bounded automata and 2) push down automata

Theory of Computation MCQ with Answers