Recursive definition of a language

866 Views Asked by At

Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria:

  1. All words in L contain the substring aa an odd number of times.
  2. All words in L are such that they do not contain substrings comprising three or more consecutive copies of the letter a (i.e. the words in L do not contain the substring aaa.).

I first wrote the language in lexicographical order then produced the following recursive definition:

rule 1: aa is L

rule 2: if w is a word in L then so is:

wb, bw, wba, abw, aabwbaa

when I recursively go through this definition I think it works, however it does not seem as 'clean' as the examples given in textbooks, is there something I have missed?