Arjun Suresh (talk | contribs) (Created page with "<math>Insert formula here</math> If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following st...") |
Arjun Suresh (talk | contribs) |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
| − | <math> | + | <metadesc> If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?</metadesc> |
If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true? | If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true? | ||
| Line 12: | Line 12: | ||
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
| − | Since, the strings of <math>L</math> can be enumerated it means <math>L</math> | + | Since, the strings of <math>L</math> can be enumerated it means <math>L</math> is recursively enumerable. That is we have a <math>TM</math> which accepts all strings in <math>L</math>. Now, to be recursive the <math>TM</math> should reject all strings not in <math>L</math>. Since, the strings of the language can be enumerated in lexicographic order, it's easy to do this. For any word <math>w</math>, if we see a word in the enumeration which is lexicographically higher than <math>w</math> but no <math>w</math>, it means <math>w</math> is not in the language. This makes <math>L</math> '''recursive'''. |
| − | Now, why | + | Now, why <math>L</math> need not be context free? Consider <math>L = \{a^nb^nc^n | n\ge 0\}</math>. The strings of this language can be enumerated in lexicographic order. But we know <math>L</math> is not context free as no <math>PDA</math> can accept <math>L</math>. |
| Line 21: | Line 21: | ||
[[Category: GATE2003]] | [[Category: GATE2003]] | ||
| − | [[Category: Automata | + | [[Category: Automata questions from GATE]] |
| − | |||
If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
(A) <math>L</math> is necessarily finite
(B) <math>L</math> is regular but not necessarily finite
(C) <math>L</math> is context free but not necessarily regular
(D) <math>L</math> is recursive but not necessarily context free
Since, the strings of <math>L</math> can be enumerated it means <math>L</math> is recursively enumerable. That is we have a <math>TM</math> which accepts all strings in <math>L</math>. Now, to be recursive the <math>TM</math> should reject all strings not in <math>L</math>. Since, the strings of the language can be enumerated in lexicographic order, it's easy to do this. For any word <math>w</math>, if we see a word in the enumeration which is lexicographically higher than <math>w</math> but no <math>w</math>, it means <math>w</math> is not in the language. This makes <math>L</math> recursive.
Now, why <math>L</math> need not be context free? Consider <math>L = \{a^nb^nc^n | n\ge 0\}</math>. The strings of this language can be enumerated in lexicographic order. But we know <math>L</math> is not context free as no <math>PDA</math> can accept <math>L</math>.
<math>Insert formula here</math> If the strings of a language <math>L</math> can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true?
(A) <math>L</math> is necessarily finite
(B) <math>L</math> is regular but not necessarily finite
(C) <math>L</math> is context free but not necessarily regular
(D) <math>L</math> is recursive but not necessarily context free
Since, the strings of <math>L</math> can be enumerated it means <math>L</math>' is recursively enumerable. That is we have a <math>TM</math> which accepts all strings in <math>L</math>. Now, to be recursive the <math>TM</math> should reject all strings not in <math>L</math>. Since, the strings of the language can be enumerated in lexicographic order, it's easy to do this. For any word <math>w</math>, if we see a word lexicographically lower than <math>x</math> and a word which is lexicographically higher than <math>x</math> but no <math>w</math>, in the enumeration, it means <math>w</math> is not in the language. This makes <math>L</math> recursive.
Now, why is <math>L</math> not context free? Consider <math>L = \{a^nb^nc^n | n\ge 0\}</math>. The strings of this language can be enumerated in lexicographic order. But we know <math>L</math> is not context free as no <math>PDA</math> can accept <math>L</math>.
GATECSE