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

  • $\begingroup$ 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 $\endgroup$
    – Henry
    Sep 9, 2022 at 10:10
  • $\begingroup$ Can you please explain how a superset of words can be used to generate L? $\endgroup$ Sep 9, 2022 at 10:34
  • $\begingroup$ Take S as the superset of anything generatable from $\Sigma$ including the empty string, and then use ab as a prefix or a suffix $\endgroup$
    – Henry
    Sep 9, 2022 at 10:45
  • $\begingroup$ 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$. $\endgroup$
    – Sam
    Sep 9, 2022 at 12:23


You must log in to answer this question.

Browse other questions tagged .