Arjun Suresh (talk | contribs) (Created page with " 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, the...") |
(No difference)
|
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 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.
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 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.
GATECSE