Test by Bikram | Mock GATE | Test 2 | Question: 19

Question

Consider a language $L$ that is recognized by a machine $M$. Which of the following statements might not be true?

• A. If $M$ is a deterministic finite automaton, then $L$ can be represented by a regular expression.
• B. If $M$ is a Turing machine, then $L$ is recursive.
• C. If $M$ is a deterministic pushdown automaton, then $L$ can be represented by a context-free grammar.
• D. If $M$ is a non-deterministic pushdown automaton, then $L$ is recursively enumerable.

Comments

what exactly "might not be true" means?

---

@Vinay

Might not true means not true always ..

in case of option B it is might not true,  because if L is recognized by Turing machine M, then this only implies that L is recursively enumerable.

It does not imply that L is recursive, since M might not be able to decide L.

Answer 1

The Chomsky hierarchy of language classes and the corresponding machines that decide them.

Regular languages are the simplest. L is regular if and only if there exists a deterministic finite state automaton M that decides L.

Also, L is regular if and only if there exists a nondeterministic finite state automaton M that decides L. Finally, L is regular if and only if there exists a regular expression E such that E generates a string w if and only if w is an element of L.

All regular languages are context free. L is context free if and only if there exists a nondeterministic pushdown automaton M that decides L. (Note: The class of languages decided by deterministic pushdown automata is a strict subset of the class of context free languages.)
L is context free if and only if there exists a context free grammar G such that G generates a string w if and only if w is an element of L.

All context free languages are recursive. L is recursive if and only if there exists a Turing machine M that decides L. (It appears that the decidable languages are not technically a member of the Chomsky hierarchy, but they fit in there nicely.)

All recursive languages are recursively enumerable. L is recursively enumerable if and only if there exists a Turing machine M that recognizes L.

Choice B is not true because if L is recognized by Turing machine M, then this only implies that L is recursively enumerable. It does not imply that L is recursive, since M might not be able to decide L.

Comments

Choice B is not true because if L is recognized by Turing machine M, then this only implies that L is recursively enumerable. It does not imply that L is recursive, since M might not be able to decide L.

it above correct sentence?

According to my understanding if TM recognize some language it means that language is recursive.

Answer 2

how?

in option D,

it is CFl then it RE also.

so why not option D?

Comments

your own answer says that D is true, we need which is NOT TRUE.

---

Ohh Sorry,

got it!!