# Give a recursive definition of the following language

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

• I suspect you either need (a) two sets of words recursively defined which combine to give L or (b) a superset of words (some not in L) from which words in L can be generated Sep 9, 2022 at 10:10
• Can you please explain how a superset of words can be used to generate L? Sep 9, 2022 at 10:34
• Take S as the superset of anything generatable from $\Sigma$ including the empty string, and then use ab as a prefix or a suffix Sep 9, 2022 at 10:45
• Maybe what you want is a formal grammar for L? Like: $\Sigma \rightarrow S, S\rightarrow ab, S\rightarrow Tab, S\rightarrow abT, T\rightarrow TT, T\rightarrow a, T\rightarrow b$.
– Sam
Sep 9, 2022 at 12:23