COMPUTER SCIENCE AND ENGINEERING
COMPILER DESIGN
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
If P & R are regular and also given that if PQ=R, then
|
|
Q has to be regular
|
|
|
Q cannot be regular
|
|
|
Q need not be regular
|
|
|
Q has to be a CFL
|
Explanation:
Detailed explanation-1: -If P & R are regular and also given that if PQ=R, thena)Q has to be regularb)Q cannot be regularc)Q need not be regulard)Q has to be a CFLCorrect answer is option ‘C’.
Detailed explanation-2: -Solution: Since any string of even length can be expressed as the concatenation of strings of length 2 and since the strings of length 2 are aa, ab, ba, bb, a regular expression corresponding to the language is ( aa + ab + ba + bb )*.
Detailed explanation-3: -The intersection of a context-free language and a regular language is context-free (Theorem 3.5. 2). The idea of the proof is to simulate a push-down automaton and a finite state automaton in parallel and only accept if both machines accept.
There is 1 question to complete.