Give a recursive definition of the following language

183 Views Asked by At

Give a recursive definition of a language containing all words from Σ={a, b} which start by the substring ab or end by the substring ab.

I was asked to solve this problem using the three step recursive definition method,but I cant think a proper logic to defined this language recursively

I have tried defining this language in the following way:

  1. ab is in Language L
  2. If x is in language L then so are ax and bx
  3. No other words are in L except those defined in above two rules

But this logic does make substrings ending with ab and not those starting with ab