Select all of the statements below which are TRUE: Let L be a language defined o
ID: 3779707 • Letter: S
Question
Select all of the statements below which are TRUE: Let L be a language defined on sigma Assume that there exists a Turing Machine M that accepts L and that halts on even' string w in sigma^+. Then L is a RE language. Any language L is either REG, DCF, CF, CS, REC, or RE. If L is a CF language, then L is a REC language. For any language, L defined on the alphabet sigma, there exists a TM that accepts L. {a^n b^n c^n: n greaterthanorequalto 1} is a CS language and is not a CF language. Let L = (w w^R: W element {a, b}*} The language L is DCF, CF, CS, REC, and RE.Explanation / Answer
(c) If L is a CF language, then L is a REC language is True. Since context-free languages are a proper subset of the recursive languages and the recursive languages are a proper subset of the recursively enumerable languages. So every context free language is a recursive enumerable language.
(d) For any language L defined on the alphabet , there exist a TM that accepts L is True. Let be an alphabet and L a language over . Let M = (Q, , , , 2, q0, F) be a Turing machine. We say that M decides L if for every w there is a q Q and u, v with q0w uqv. Furthermore, q F, iff w L.
(e) {anbncn, n>= 1} is a Context Sensitive language and is not a Context free language is True because every description of a context-free language is of finite length, so there are a countably infinite number of such descriptions.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.