Question: Given any language L that does not include , let us define its cousin language I L I as follows: For any string of a's
Given any language L that does not include Λ, let us define its cousin language I L I as follows: For any string of a's and b's, if the word formed by concatenating the second, fourth, sixth, . . . letters of this string is a word in L, then the whole string is a word in I L I . For instance, if bbb is a word in L, then ababbbb and bbababa are both words in I L I .
(i) Show that if there is some PDA that accepts L, then there is some PDA that accepts I L I.
(ii) If L is re gular, is I L I necessarily re gular too?
Step by Step Solution
3.44 Rating (173 Votes )
There are 3 Steps involved in it
i This is because if there is a PDA that accepts L then this PDA can ... View full answer
Get step-by-step solutions from verified subject matter experts
