Different approach for an enumerator

Re: Different approach for an enumerator

by Giorgio Satta -
Number of replies: 0

Dear Arash, I think you must have taken a course in formal languages and automata in your bachelor, since you are using concepts that we did not discuss in this class.

I know what an enumerator is, but we have not introduced this notion in class. Please when you come to final exam use only concepts that are mentioned in the syllabus / were discussed in class, do not depart from that.

Coming back to your question, just say that the language L is infinite, which necessarily means it has strings of unbounded length. According to what was done in this course, we have two ways of describing language L.

  • First, we can write a PDA (recogniser) that for an arbitrary string w in input will decide whether w is in L or not.
  • Second, we can write a CFG (generative) that generates all strings of L.

Remember that every string w in L has a finite length, by the very definition of string. Thus we can generate w in finite time with our CFG, and we can recognise w in finite time with our PDA. This is true no matter what the length of w is, since we know that the length is always finite.

Please try to reformulate your original question in the framework outlined above.