Automata qn 3 - Revision history

Arjun Suresh at 14:01, 2 September 2014

2014-09-02T14:01:03Z

Arjun Suresh at 11:24, 15 July 2014

2014-07-15T11:24:53Z

Arjun Suresh at 09:25, 14 July 2014

2014-07-14T09:25:14Z

Arjun Suresh at 22:39, 13 July 2014

2014-07-13T22:39:30Z

Arjun Suresh at 09:42, 7 July 2014

2014-07-07T09:42:57Z

Arjun Suresh at 16:40, 3 June 2014

2014-06-03T16:40:04Z

Arjun Suresh at 12:55, 15 May 2014

2014-05-15T12:55:55Z

Arjun Suresh: /* Solution */

2014-01-31T02:23:10Z

‎Solution

Arjun Suresh at 02:22, 31 January 2014

2014-01-31T02:22:39Z

Arjun Suresh at 02:22, 31 January 2014

2014-01-31T02:22:20Z

@@ Line 1: / Line 1: @@
-Let <math>Σ = \{a, b, c\}</math>. Which of the following statements is true ?
+a)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx | x ∊ A\}$
-a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx | x ∊ A\}</math>
+'''b)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x | xx ∊ A\}$'''
-'''b)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{x | xx ∊ A\}</math>'''
+c)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx | x ∊ A\}$
-c)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{xx | x ∊ A\}</math>
+d)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x | xx ∊ A\}$
 ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
-We can get a DFA for <math>L = \{x | xx ∊ A\}</math> as follows:
+We can get a DFA for $L = \{x | xx ∊ A\}$ as follows:
-Take DFA for <math>A</math> $(Q, \delta, \Sigma, S, F)$ with everything same except initially making $F = \phi$.
+Take DFA for $A$ $(Q, \delta, \Sigma, S, F)$ with everything same except initially making $F = \phi$.
-Now for each state $D \in Q$, consider 2 separate DFAs, one with <math>S</math> as the start state and <math>D</math> as the final state and another with <math>D</math> as the start state and set of final states $⊆ F$. If both these DFAs accept same language make <math>D</math> as final state.
+Now for each state $D \in Q$, consider 2 separate DFAs, one with $S$ as the start state and $D$ as the final state and another with $D$ as the start state and set of final states $⊆ F$. If both these DFAs accept same language make $D$ as final state.
 This procedure works as checking the equivalence of 2 DFAs is decidable.
@@ Line 19: / Line 18: @@
 '''Contradictions for other choices'''
-a) Consider <math>A =  Σ^*</math>. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
+a) Consider $A =  Σ^*$. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
 c) Same example as for (a)

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

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

@@ Line 26: / Line 26: @@
 This is CFL. But if we make L from A as per (d), it'll be
 $L = \{a^nb^nc^n|n\ge0\}$ which is not context free..
@@ Line 38: / Line 33: @@
 {{Template:FBD}}
 [[Category: Automata questions]]
-[[Category: Questions]]
+[[Category: Non-GATE Questions]]

@@ Line 38: / Line 38: @@
 {{Template:FBD}}
 [[Category: Automata questions]]
 [[Category: Questions]]

← Older revision		Revision as of 02:22, 31 January 2014
Line 1:		Line 1:

−	Let <math>Σ = {a, b, c}</math>. Which of the following statements is true ?	+	Let <math>Σ = \{a, b, c\}</math>. Which of the following statements is true ?

	a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx \| x ∊ A\}</math>		a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx \| x ∊ A\}</math>

@@ Line 1: / Line 1: @@
-Let Σ = {a, b, c}. Which of the following statements is true ?
+Let <math>Σ = {a, b, c}</math>. Which of the following statements is true ?
-a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}
+a)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{xx | x ∊ A\}</math>
-'''b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}'''
+'''b)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is regular, then so is <math>\{x | xx ∊ A\}</math>'''
-c)For any A ⊆ Σ*, if A is context-free, then so is {xx | x ∊ A}
+c)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{xx | x ∊ A\}</math>
-d)For any A ⊆ Σ*, if A is context-free, then so is {x | xx ∊ A}
+d)For any <math>A ⊆ Σ^*</math>, if <math>A</math> is context-free, then so is <math>\{x | xx ∊ A\}</math>
 ===Solution===
-We can get a DFA for L = {x | xx ∊ A} as follows:
+We can get a DFA for <math>L = \{x | xx ∊ A\}</math> as follows:
-Take DFA for A $(Q, \delta, \Sigma, S, F)$ with everything same except initially making F = {}.
+Take DFA for <math>A</math> $(Q, \delta, \Sigma, S, F)$ with everything same except initially making $F = \phi$.
-Now for each state $D \in Q$, consider 2 separate DFAs, one with S as the start state and D as the final state and another with D as the start state and set of final states ⊆ F. If both these DFAs accept same language make D as final state.
+Now for each state $D \in Q$, consider 2 separate DFAs, one with <math>S</math> as the start state and <math>D</math> as the final state and another with <math>D</math> as the start state and set of final states $⊆ F$. If both these DFAs accept same language make <math>D</math> as final state.
 This procedure works as the equivalence of 2 DFAs is decidable.
@@ Line 19: / Line 19: @@
 '''Contradictions for other choices'''
-a) Consider A =  Σ*. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
+a) Consider <math>A =  Σ^*</math>. Now for $w \in A,  L = \{xx | x \in A\} = \{ww | w \in Σ^*\} $ which is context sensitive
 c) Same example as for (a)