Arjun Suresh (talk | contribs) (→Solution) |
Arjun Suresh (talk | contribs) (→Solution) |
||
| Line 12: | Line 12: | ||
===Solution=== | ===Solution=== | ||
We can get a DFA for L = {x | xx ∊ A} as follows: | 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 imitially making F = {}. 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 final state | + | Take DFA for A $(Q, \delta, \Sigma, S, F)$ with everything same except imitially making F = {}. 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 final state ⊆ F. If both these DFAs accept same language make D as final state. |
This procedure works as the equivalence of 2 DFAs is decidable. | This procedure works as the equivalence of 2 DFAs is decidable. | ||
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}
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 imitially making F = {}. 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 final state ⊆ F. 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 \in 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..
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}
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 imitially making F = {}. 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 final state $\subset F$. 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 \in 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..
GATECSE