2.25 For any language (A), let SUFFIX(A) = { v | uv ∈ A for some string u }. Show that the class of CFLs is closed under the SUFFIX operation.
Hint: Add epsilon transitions to skip symbols.
Solution: For every state A, add a state A′. And new start state will be S′. For every transition δ(A,0,a) → (B,b) add a transition δ(A′,ε,a) → (B′,b). And δ(A′,ε,ε) → (A,ε).
Hint: Add epsilon transitions to skip symbols.
Solution: For every state A, add a state A′. And new start state will be S′. For every transition δ(A,0,a) → (B,b) add a transition δ(A′,ε,a) → (B′,b). And δ(A′,ε,ε) → (A,ε).
No comments:
Post a Comment