(Solution)
 
(20 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
Let $Σ = \{a, b, c\}$. Which of the following statements is true ?
  
Let Σ = {a, b, c}. Which of the following statements is true ?
+
a)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{xx | x ∊ A\}$
  
a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}
+
'''b)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x | xx ∊ A\}$'''
  
'''b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}'''
+
c)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx | x ∊ A\}$
  
c)For any A ⊆ Σ*, if A is context-free, then so is {xx | x ∊ A}
+
d)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x | xx ∊ A\}$
  
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 $L = \{x | xx ∊ A\}$ as follows:
 +
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 $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.
  
===Solution===
+
This procedure works as checking the equivalence of 2 DFAs is decidable.
We can get a DFA for L as follows:
 
Take DFA for A. Let S be its start state.
 
For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.
 
 
 
This procedure works as the equivalence of 2 DFAs is decidable.
 
  
 
'''Contradictions for other choices'''
 
'''Contradictions for other choices'''
  
a) Consider A =  Σ*. Now for $w \in A,  L = \{xx | x 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)
 
c) Same example as for (a)
  
d) $\{a^nb^nc^*a^*b^nc^n|n>0\} $
+
d)Consider $A = \{a^nb^nc^*a^*b^nc^n|n\ge0\} $
 
This is CFL. But if we make L from A as per (d), it'll be  
 
This is CFL. But if we make L from A as per (d), it'll be  
L = {a^nb^nc^n|n>0} which is not context free..  
+
$L = \{a^nb^nc^n|n\ge0\}$ which is not context free..  
 
 
 
 
 
 
 
 
 
 
  
  
Line 38: Line 32:
 
{{Template:FBD}}
 
{{Template:FBD}}
  
[[Category:Automata Theory]]
+
[[Category: Non-GATE Questions from Automata Theory]]
[[Category: Questions]]
 

Latest revision as of 14:01, 2 September 2014

Let $Σ = \{a, b, c\}$. Which of the following statements is true ?

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

b)For any $A ⊆ Σ^*$, if $A$ is regular, then so is $\{x | xx ∊ A\}$

c)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{xx | x ∊ A\}$

d)For any $A ⊆ Σ^*$, if $A$ is context-free, then so is $\{x | xx ∊ A\}$

Solution by Arjun Suresh

We can get a DFA for $L = \{x | xx ∊ A\}$ as follows: 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 $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.

Contradictions for other choices

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)

d)Consider $A = \{a^nb^nc^*a^*b^nc^n|n\ge0\} $ 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..






blog comments powered by Disqus

Let Σ = {a, b, c}. Which of the following statements is true ?

a)For any A ⊆ Σ*, if A is regular, then so is {xx | x ∊ A}

b)For any A ⊆ Σ*, if A is regular, then so is {x | xx ∊ A}

c)For any A ⊆ Σ*, if A is context-free, then so is {xx | x ∊ A}

d)For any A ⊆ Σ*, if A is context-free, then so is {x | xx ∊ A}

Solution[edit]

We can get a DFA for L as follows: Take DFA for A. Let S be its start state. For each state D of A, 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 final state in final states of A. If both these DFAs accept same language make D as final state.

This procedure works as the equivalence of 2 DFAs is decidable.

Contradictions for other choices

a) Consider A = Σ*. Now for $w \in A, L = \{xx | x ∊ A\} = \{ww | w \in Σ^*\} $ which is context sensitive

c) Same example as for (a)

d) $\{a^nb^nc^*a^*b^nc^n|n>0\} $ This is CFL. But if we make L from A as per (d), it'll be L = {a^nb^nc^n|n>0} which is not context free..








blog comments powered by Disqus