[Solved] Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?

Q.	Let P be a regular language and Q be context-free language such that Q ∈ P. (For example, let P be the language represented by the regular expression pq and Q be {pnqn n∈ N}). Then which of the following is ALWAYS regular?
A.	P ∩ Q
B.	P – Q
C.	∑* – P
D.	∑* – Q
Answer» C. ∑* – P

1.3k

Do you find this helpful?

View all MCQs in

Theory of Computation

Discussion

No comments yet

Related MCQs

A language is represented by a regular expression (a)*(a + ba). Which of the following strings does not belong to the regular set represented by the above expression?
Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
Let L be any infinite regular language, defined over an alphabet Σ then there exist three strings x, y and z belonging to Σ such that all the strings of the form XY^ n Z for n=1,2,3, … are the words in L called
How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
Which of the following are decidable? 1) Whether the intersection of two regular language is infinite. 2) Whether a given context free language is regular. 3) Whether two push down automata accept the same language. 4) Whether a given grammar is context free.
Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true?
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?
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 ?
Let L={w (0 + 1)* w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?