To your question:
Imagine a * b * to be regular, is there evidence that it is regular or not?
No need to imagine, the expression a*b* is called r egular e xpression a> (re), and regular expressions are possible only for regular languages. If the language is not regular, then regular expression is also impossible for it, and if the language is a regular language, we can always represent it with some regular expression.
Yes, a*b* is a common language.
Description of the language : any number a followed by any digits b (by any number I mean zero (including null ^ ) or more times). Some examples of strings:
{^, a, b, aab, abbb, aabbb, ...}
The DFA for RE a*b* will look like this:
a- b- || || ▼| ▼| ---►((Q0))---b---►((Q1)) In figure: `(())` means final state, so both `{Q0, Q1}` are final states.
You need to understand the following basic concept:
What is a regular language? And why the infinite language `a * b *` is regular, while languages like `{a n b n | n> 0} `are not regular !!
A language (set) is called a regular language if it requires only a limited (finite) amount of information to be stored in any instance of time when processing language strings.
So what is "limited" information? For example: consider the fan switch 'on' / 'off'. When viewing the fan switch, you can tell whether the fan is on or off (this is limited or limited information). But we cannot say that “how many times” the fan has been turned on and off in the past! (to remember, a mechanism is needed to store an "unlimited" amount of information for counting, "how many times", for example, some meter uses in our cars / bikes).
Language {a n b n | n> 0} is not a regular language, because here n unlimited (it can be infinite large). To check strings in the language a n b n we need to remember how many characters a were found, and this requires infinite memory for counting, because the number of characters a in a string can be infinitely large!
This means that an automaton is able to process only lines of the language a n b n if it has infinite memory, for example, PDA.
While a*b* is regular in nature, because there is a limited restriction and dash; that b may appear after some a (and a cannot appear after b ). And therefore, each line of this language can be easily processed (or recognized) by automata in which we have finite memory, and finite automata are a class of automata where memory is finite. Yes, in finite state machines we have a finite amount of memory in terms of states.
(The memory in finite automata is present in the form of states Q and in accordance with the main automaton: any automata can have only finite states, therefore finite automata have finite memory, therefore the class of automata for regular languages called finite automata. You can think of finite automata, such like a CPU without memory, which have a finite register for storing its internal states)
Final state ⇒ Final memory ⇒ Only a language can be a process for which final memory should be stored at any time during string processing ⇒ this language is called Regular Language
The lack of external memory is a limitation of finite automation ⇒ or we can say that the limitation of finite state machines is determined by a class of language called Regular Language.
You must read another answer, “finiteness of a regular language,” in order to find out the volume of a regular language.
side note ::
- language {a n b n | n> 0} is a subset of
a*b* - Also the language {a n b n | 10 > 100 n> 0} is a regular, large set, but regular, since
n bounded, therefore finite automata and a regular expression are possible for this language.
You should also read: How to prove that a language is regular?