A substitution is the action of taking a language L and two strings of terminals

Question

A substitution is the action of taking a language L and two strings of terminals called sa and st and changing every word of L by substituting the string sa for each a and the string sb for each b in the word. This turns L into a completely new language. Let us say, for example, that L was the language defined by the regular expression a*(bab + aa)* and say that Then L would become the language defined by the regular expression (i) Prove that after any substitution any regular language is still regular. (i) Prove that after any substitution a CFL is still context-free.

Explanation / Answer

Solution:

i)

Since we know that a regular language is acceptable by a finite state machine which means for every regular language there is an FSM which will accept the language.

Now, since we re using substitution here which means we are replacing the recursive part of the regular expression with the next step of the recursion, or we can say that we are pumping the string.

So, if a language which is acceptable by a finite state machine then it will be even acceptable by the same finite machine because we are not changing the state, we can pump it there any number of time and the language will be acceptable by the same FSM.

This proves that the language will be still regular language.

ii)

Just like above a context-free language is acceptable by a Pushdown automaton and even after pumping the string it will be still acceptable by the same push-down automata

Which proves that the language will still be a context-free language.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.