COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
I. Whether the intersection of two regular languages is infinite
|
|
|
II. Whether a given context-free language is regular
|
|
|
III. Whether two push-down automata accept the same language
|
|
|
IV. Whether a given grammar is context-free
|
Detailed explanation-1: -The equality problem is Undecidable for all languages except in the case of finite automata (i.e. for regular languages) & Deterministic context-free language. Checking whether a language of context-free grammar is non-empty is Decidable.
Detailed explanation-2: -Membership problem in CFL is decidable using CYK algorithm to check the membership. To check whether a given CFL is regular or not in undecidable.
Detailed explanation-3: -A grammar is context-free if left-hand sides of all productions contain exactly one non-terminal symbol. By definition, if one exists, then the language is context-free. An equivalent construct would be a pushdown automaton.
Detailed explanation-4: -(a) True, since every regular language is context-free, every context-free language is decidable, and every decidable language is Turing-recognizable.
Detailed explanation-5: -A language L is decidable if there exists a Turing machine M such that M(w)=ACCEPT accepts IFF w∈L and M always halts.