Regular language

Question

A^n | n>=1

In this language 'n' is unbounded so I want to understand why it comes under finite automata as language is infinite.

As finite automata has finite memory.

Please suggest

 

Thanks

Mayank

Comments

you are not storing them..

Just you are checking the condition.

---

@shaik @aambazinga

Self-Loop on state means it can be infinite noe?

My confusion is every transaction from one state to other is considered as saving in memory.

Then why for self loop we are not storing.

Please suggest

---

Storage is required when we will be needing that object in future. Why would you store anything when we don't need them. Do we?

Similarly, In finite automata, when there is loop at any state, it simply meant '*' in regular expression- means we are not caring about how many times that particular substring produced by that particular subexpression appears in the string generated. If we are not caring, we will not store them.

Answer 1

See, it has never been said that an infinite language can't be regular.

For a language to be regular, it should satisfy kleens's theorem, which is two way.

That is, a language is regular iff it can be obtained from finite language by applying  three operations- union, concatenation and Kleene star.

Also a language is regular iff regular expression, regular grammar, finite automata exist for it.

Comments

Thanks

Answer 2

A language (a set) L is called Regular Language, if its require bounded (finite) amount of information at any instance of time while processing a strings in language L.

What is bounded information?
For example: Consider a fan switch for on-off. By viewing fan-switch we can say whether fan is in on or off state (this is bounded or limited information).
But we can not know that how many times a fan has been on-off in past! (to memorized, it requires a mechanism to store unbounded amount of information to count how many times – e.g. some kind of meters, we have in our car/bike).

But for $a^n|n\geq1$ is regular by its nature, because there is bounded restriction that "string consists of only symbol 'a'  And strings of this language can be easily processed (or recognized) by an automata in which we have finite memory that is finite automata. Yes, in finite automata we have finite memory in terms of states (The word "Finite" significance of the presence of 'finite amount of memory' in the form of finite number of states Q).