GATE2003 q15 - Revision history

Arjun Suresh at 13:53, 24 August 2014

2014-08-24T13:53:50Z

Arjun Suresh at 13:52, 24 August 2014

2014-08-24T13:52:19Z

Arjun Suresh at 11:20, 15 July 2014

2014-07-15T11:20:56Z

Arjun Suresh at 09:43, 7 July 2014

2014-07-07T09:43:19Z

Arjun Suresh at 15:53, 17 June 2014

2014-06-17T15:53:43Z

Arjun Suresh at 07:10, 15 April 2014

2014-04-15T07:10:23Z

Arjun Suresh: /* Solution */

2014-02-16T12:40:50Z

‎Solution

Arjun Suresh: /* Solution */

2014-02-05T14:24:25Z

‎Solution

Arjun Suresh at 12:26, 5 February 2014

2014-02-05T12:26:56Z

Arjun Suresh at 12:24, 5 February 2014

2014-02-05T12:24:21Z

← Older revision		Revision as of 13:53, 24 August 2014
Line 15:		Line 15:
	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'''.		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 is <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>.	+	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 13: / Line 13: @@
 ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
-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>x</math> but no <math>w</math>, it means <math>w</math> is not in the language.  This makes <math>L</math> '''recursive'''.
+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 is <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>.

← Older revision		Revision as of 11:20, 15 July 2014
Line 21:		Line 21:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	[[Category: Automata questions]]	+	[[Category: Automata questions from GATE]]

← Older revision		Revision as of 09:43, 7 July 2014
Line 21:		Line 21:

	[[Category: GATE2003]]		[[Category: GATE2003]]
−	~~[[Category: Automata Theory]]~~
	[[Category: Automata questions]]		[[Category: Automata questions]]

← Older revision		Revision as of 15:53, 17 June 2014
Line 12:		Line 12:


−	===~~Solution~~===	+	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
	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>x</math> but no <math>w</math>, it means <math>w</math> is not in the language. This makes <math>L</math> '''recursive'''.		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>x</math> but no <math>w</math>, it means <math>w</math> is not in the language. This makes <math>L</math> '''recursive'''.

@@ Line 22: / Line 22: @@
 [[Category: GATE2003]]
 [[Category: Automata Theory]]
-[[Category: Previous year GATE questions]]
+[[Category: Automata questions]]

← Older revision		Revision as of 14:24, 5 February 2014
Line 15:		Line 15:
	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 lower than <math>x</math> and a word which is lexicographically higher than <math>x</math> but no <math>w</math>, it means <math>w</math> is not in the language. This makes <math>L</math> '''recursive'''.		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 lower than <math>x</math> and a word which is lexicographically higher than <math>x</math> but no <math>w</math>, 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>.	+	Now, why is <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 13: / Line 13: @@
 ===Solution===
-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'''.
+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 lower than <math>x</math> and a word which is lexicographically higher than <math>x</math> but no <math>w</math>, 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>.

← Older revision		Revision as of 12:24, 5 February 2014
Line 1:		Line 1:
−	<math>~~Insert formula here~~</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?