Automata qn 4 - Revision history

Arjun Suresh at 10:42, 10 August 2015

2015-08-10T10:42:45Z

Arjun Suresh at 10:15, 6 August 2014

2014-08-06T10:15:29Z

Arjun Suresh at 11:24, 15 July 2014

2014-07-15T11:24:42Z

Arjun Suresh at 09:25, 14 July 2014

2014-07-14T09:25:26Z

Arjun Suresh at 22:40, 13 July 2014

2014-07-13T22:40:11Z

Arjun Suresh at 09:43, 7 July 2014

2014-07-07T09:43:08Z

Arjun Suresh at 16:40, 3 June 2014

2014-06-03T16:40:19Z

Arjun Suresh at 14:06, 14 April 2014

2014-04-14T14:06:26Z

Arjun Suresh at 20:09, 19 February 2014

2014-02-19T20:09:23Z

Arjun Suresh: /* Solution */

2014-02-19T20:06:37Z

‎Solution

@@ Line 1: / Line 1: @@
 Consider the following languages
-<math>A=\{M| TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>
+<math>A=\{M \mid TM</math> <math> M</math> accepts at most 2 distinct inputs<math>\}</math>
-<math>B=\{M|TM</math> <math> M</math> accepts more than 2 distinct inputs<math>\}</math>
+<math>B=\{M \mid TM</math> <math> M</math> accepts more than 2 distinct inputs<math>\}</math>
 Identify the correct statement from the following:

@@ Line 18: / Line 18: @@
 ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
-<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. HThus, <math>T_A</math> may not output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>A</math> is  not Turing recognizable.
+<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Thus, <math>T_A</math> may not output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>A</math> is  not Turing recognizable.
 Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use [http://www.xamuel.com/dovetailing/ dovetailing] technique so that even if some string causes <math>TM</math> to loop forever, we can continue progress).  If <math>M</math> is accepting more than 2 distinct inputs we are sure that we'll  encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>B</math> is Turing recognizable.

@@ Line 27: / Line 27: @@
 {{Template:FBD}}
-[[Category: Automata questions]]
 [[Category: Non-GATE Questions from Automata Theory]]

@@ Line 28: / Line 28: @@
 {{Template:FBD}}
 [[Category: Automata questions]]
-[[Category: Non-GATE Questions]]
+[[Category: Non-GATE Questions from Automata Theory]]

@@ Line 28: / Line 28: @@
 {{Template:FBD}}
 [[Category: Automata questions]]
-[[Category: Questions]]
+[[Category: Non-GATE Questions]]

← Older revision		Revision as of 14:06, 14 April 2014
Line 17:		Line 17:


−	===~~Solution~~===	+	==={{Template:Author\|Arjun Suresh\|{{arjunweb}} }}===
	<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. HThus, <math>T_A</math> may not output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>A</math> is not Turing recognizable.		<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. HThus, <math>T_A</math> may not output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>A</math> is not Turing recognizable.

@@ Line 18: / Line 18: @@
 ===Solution===
-<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output <math>"yes"</math> for "<math>yes</math>" cases of the language and hence <math>A</math> is not Turing recognizable.
+<math>A</math> is Turing recognizable if <math>TM</math> for <math>A</math>, say <math>T_A</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>A</math>- i.e.; when <math>M</math> accepts at most 2 distinct inputs. But <math>M</math> can loop forever without accepting more than 2 distinct inputs and we can never be sure if it will or will not accept any more input. Hence, <math>T_A</math> may not output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>A</math> is not Turing recognizable.
 Similarly, <math>B</math> is Turing recognizable if <math>TM</math> for <math>B</math>, say <math>T_B</math> outputs "<math>yes</math>" for "<math>yes</math>" cases of <math>B</math>- i.e.; when <math>M</math> accepts more than 2 distinct inputs. If <math>M</math> is accepting more than 2 distinct inputs, it's possible to enumerate all strings from the language (strings of length 1 followed by strings of length 2 and so on ) and feed to <math>M</math>. (We should use [http://www.xamuel.com/dovetailing/ dovetailing] technique so that even if some string causes <math>TM</math> to loop forever, we can continue progress).  If <math>M</math> is accepting more than 2 distinct inputs we are sure that we'll  encounter those strings after some finite moves of the <math>TM</math>. Thus <math>T_B</math> can always output "<math>yes</math>" for "<math>yes</math>" cases of the language and hence <math>B</math> is Turing recognizable.