Define recursively the language L of all finite strings over the alphabet Σ={a b} satisfying both criteria:
- All words in L contain the substring aa an odd number of times.
- 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?