Question: is there a different approach for an enumerator that is an unbounded language vs a finite language. My problem specifically asks for a high level description. Like say that the language L ={a^ b^(2n) | n >= 0}. So n is unbounded and therefore infinite. if I can make a PDA for it then it must be a CFL and specifically a dPDL so it's a dCFL. So it's decidable but I am not understanding that given a sufficiently large input, potentially forever, how it would halt.
In reply to ARASH ABDOLHOSSEIN POUR MALEKSHAH
Re: Different approach for an enumerator
by Giorgio Satta -
Before I answer your questions, please clarify a few points:
- what is an enumerator?
- what does it mean n is infinite?
- infinite input in your use of forever ... recall that any input must be a string and therefore a finte sequence, computation will therefore end at some point
I am also confused by your use of deterministic PDA and deterministic CFL: we have never mentioned these notions in our lectures, they are not part of the syllabus ...
In reply to Giorgio Satta
Re: Different approach for an enumerator
Dear professor Satta
first of all, thanks for your time and sorry for my delay.
please let me explain completely my question.
1. enumerator is a theoretical construct . It refers to a machine or algorithm that generates (enumerates) strings of a language one by one in a systematic way .
2.n is infinite. it means that the language contains strings of arbitrarily large length.
Maybe I’m just confused on the meaning of high level. How detailed exactly is high level?
I want to know that I am on the right path/train of thought. so I wrote out things I know:
a language is Turing recognizable iff L is recursively enumerable.. So there is a TM that accepts the set and there is an enumerator that enumerates L
a enumerator M is said to enumerate a string w iff at some point M prints w on the output tape
decidable: halts on all inputs. The set is a proper subset of sigma, the set is finite bound and countable. using a ND TM for all K and for all Kth partitions.
a language is decidable iff both L and L complement are Turing recognizable.
Kleene Star is closed under Turing recognizable and Turing decidable languages
I hope that i explained in correct way.
thank you so much
Arash
first of all, thanks for your time and sorry for my delay.
please let me explain completely my question.
1. enumerator is a theoretical construct . It refers to a machine or algorithm that generates (enumerates) strings of a language one by one in a systematic way .
2.n is infinite. it means that the language contains strings of arbitrarily large length.
Maybe I’m just confused on the meaning of high level. How detailed exactly is high level?
I want to know that I am on the right path/train of thought. so I wrote out things I know:
a language is Turing recognizable iff L is recursively enumerable.. So there is a TM that accepts the set and there is an enumerator that enumerates L
a enumerator M is said to enumerate a string w iff at some point M prints w on the output tape
decidable: halts on all inputs. The set is a proper subset of sigma, the set is finite bound and countable. using a ND TM for all K and for all Kth partitions.
a language is decidable iff both L and L complement are Turing recognizable.
Kleene Star is closed under Turing recognizable and Turing decidable languages
I hope that i explained in correct way.
thank you so much
Arash
In reply to ARASH ABDOLHOSSEIN POUR MALEKSHAH
Re: Different approach for an enumerator
by Giorgio Satta -
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.
In reply to ARASH ABDOLHOSSEIN POUR MALEKSHAH
Re: Different approach for an enumerator
by Giorgio Satta -
Dear Arash you have not replied to my questions ...