Given any language L that does not include , let us define its cousin language I L

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 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?

Fantastic news! We've Found the answer you've been seeking!

Step by Step Answer:

Related Book For  book-img-for-question
Question Posted: