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>
 
  
 
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
==={{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.
 
This procedure works as checking the equivalence of 2 DFAs is decidable.
Line 19: Line 18:
 
'''Contradictions for other choices'''
 
'''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)
 
c) Same example as for (a)

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 by Arjun Suresh[edit]

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