I am taking an Automata class, and I learnt that languages can be defined either recursively or by using regular expressions. I was introduced to both methods, and I learnt that Regex method is better and recursive method is outdated. I practiced some problems for recursive language definition (like defining Arithmetic Expressions and Polynomials recursively). However, I could not find more on this topic. I have searched many Automata books on internet, and almost all of them ignore this topic and focus on Regex method for describing languages. Is there any material with good information on the recursive method and practice problems for defining languages recursively?

What I mean by recursive methods is the three step method of the form

  1. a is in language L
  2. If x is a word in L, then so is xa
  3. Only those words defined by above rules are in L

The above method defines language L = {a aa aaa aaaa aaaaa......}

  • 1
    $\begingroup$ Could you give an example of a recursive method? $\endgroup$
    – ShyPerson
    Commented Sep 9, 2022 at 3:55
  • $\begingroup$ I have added an example in the question $\endgroup$ Commented Sep 9, 2022 at 9:50
  • $\begingroup$ Looks like there's not much agreement on this: math.stackexchange.com/questions/228863/… $\endgroup$
    – ShyPerson
    Commented Sep 9, 2022 at 21:41
  • $\begingroup$ From OP: "I learnt that Regex method is better and recursive method is outdated." I have no idea what the context here was; perhaps you should ask your professor what was meant by this. But recursive definitions are far more powerful than regexes, and they are not outdated. (There are many languages which can be defined recursively but which cannot be defined by regexes.) $\endgroup$ Commented Sep 10, 2022 at 19:41


You must log in to answer this question.