I know a^{n}b^{n} for n > 0 is not regular by the pumping lemma but I would imagine `a*b*`

to be regular since both a,b don't have to be the same length. Is there a proof for it being regular or not?

# Is a*b* regular

computation-theoryregular-language

#### Related Solutions

If you can correctly describe your language L by an NFA or DFA, then it will be regular.

There is a well known equality of NFAs, DFAs, regular grammars and regular expressions, so a representation of L in any of these formalisms should do.

You are not completely clear about pumping lemma.

What pumping lemma say:

Formal definition: **Pumping lemma for regular languages**

Let

be a regular language. Then there exists an integer`L`

`p`

`≥ 1`

depending only onsuch that every string`L`

in`w`

of length at least`L`

(`p`

is called the`p`

`"pumping length"`

) can be written as=`w`

(i.e.,`xyz`

can be divided into three substrings), satisfying the following conditions:`w`

`|`

`y`

`| ≥ 1`

`|`

`xy`

`| ≤`

`p`

- for all
`i`

`≥ 0`

,`xy`

^{i}`z`

`∈`

`L`

But what this statement says is that:

If a language is really a regular language then there must be *some way* to generate(*pump*) new strings from **all** *sufficiently large strings*.

means, a string in language that is of the length ≥*Sufficiently large string**P*.

_{So it may not be possible to generate new string from small strings even if language is Regular Language}means, if language is really a regular and our choice of*Some way*`w`

is correct. Then there should be*at lest one way*to break`w`

in three parts`xyz`

such that by repeating(pumping)`y`

for any number of times we can generate new strings in the language.

_{correct choice of w means: w in language and sufficiently large ≥ P}

*note*: in second point, there may be a chance that even if you breaks `w`

correctly into `xyz`

according to formal definition still some new generated strings are not in language. *As you did*.

And in this situation you are to retry with some other possible choice of `y`

.

In you chosen string `w`

= "**0000**" you can break `w`

such that `y = 00`

. And with this choice of `y`

you would always find a new generated string in in Language that is *"even number of zeros"*

_{One mistake you are doing in your proof that you are doing for a specific string 0000. You should proof for all w ≥ P. So still your proof is incomplete}

Read my this answer **IN CONTEXT OF PUMPING LEMMA FOR REGULAR LANGUAGES**

In that answer, I have explained that *breaking w into xyz and pumping y* means

*finding looping part and repeating looping part to generate new strings*in language.

When we proof that some language is regular; then actually we don't know where is the looping part so we try with all possible choices that satisfies pumping lemma's rule 1,2 & 3.

And Pumping lemma says that if language is regular and infinite them there must be a loop in the DFA and every sufficiently large string in language passes through looping part (according to pigeonhole principle) of DFA (and hence `y`

can't be null. That's rule-1 in above formal definition).

Think, loop can be at initial position or at end and so `x`

and `z`

can be null strings.

But actually we don't know where loop falls in DFA so we try with all possible ways.

**To proof a language is regular**: You are to proof that for *all** sufficiently long strings*(** w**) in language there is

*at-least*(

**one**way**) to generate new strings in the language by**

*y**repeating looping part*(

**any number****) of times.**

*i***To proof a language is not regular**:You are to find

*at least one**sufficiently*long strings (

**) in language such that there**

*w**no choice for*so that its possible to generate new strings

**any way 'y'***with*(

**all possible**repetition**).**

*i*```
To proof using Pumping Lemma:
+-------------------------+--------------------------+----------------+--------------+
| | Sufficient large W in L | y | i >=0 |
+-------------------------+--------------------------+----------------+--------------+
| language is regular | For all W (all W can use | At-least one | For all i>=0 |
| | to generate new W' in L) | | |
+-------------------------+--------------------------+----------------+--------------+
| language is NOT regular | Find Any W (at-least 1 | With all (Show | At-least one |
| | W that can't generates | no possible Y | i |
| | new W' in L | exists) | |
+-------------------------+--------------------------+----------------+--------------+
```

**CAUTION:**: The Rule always not works to proof 'Weather a Language is Regular?'

Pumping Lemma necessary but not sufficient condition for a language to be regular. A language possible that satisfies these conditions may still be non-regular.

Reference

To proof a language is regular you have some necessary and sufficient conditions for a language to be regular.

## Best Solution

Answer to your question:

No need to imagine, expression

`a*b*`

is calledregularexpression (re), and regular expressions are possible only for regular languages. If a language is not regular then regular expression is also not possible for that and if a language is regular language then we can always represent it by some regular expression.Yes,

`a*b*`

represents a regular language.Language description: Any number offollowed by any numbers of`a`

(by`b`

any numberI mean zero (including null`^`

) or more times). Some example strings are:DFA for RE

`a*b*`

will be as follows:You need to understand following basic concept:

## What is basically a regular language? And why an infinite language `a*b*` is regular whereas languages like `{ a

^{n}b^{n}| n > 0 }` are not regular!!A language(a set) is called regular language, if it requires only bounded(finite) amount of information to keep store at any instance of time while processing strings of the language.

So, what is 'bounded' information?

For example: Consider a fan 'on'/'off' switch. By viewing fan switch we can say whether the fan is in the

`on`

or`off`

state (this is bounded or limited information). But we cannot tell 'how many times' a fan has been switched to`on`

or`off`

in the past! (to memorize this, we require a mechanism to store an 'unbounded' amount of information to count — 'how many times' e.g. the meter used in our cars/bikes).The language { a

^{n}b^{n}| n > 0 } isnota regular language because here`n`

is unbounded(it can be infinitely large). To verify strings in the language a^{n}b^{n}, we need to memorize how manysymbols there are and it requires an infinite memory storage to count because the number of`a`

symbols in the string can be infinitely large!`a`

That means an automata is only capable of processing strings of the language a

^{n}b^{n}if it has infinite memory e.g PDA.Whereas,

`a*b*`

is of course regular by its nature, because there is the bounded restriction ‐ thatmay come after some`b`

( and`a`

`a`

can't came after`b`

). And that is why every string of this language can be easily processed (or recognized) by an automata in which we have finite memory - andfinite automatais a class of automata where memory is finite. Yes, in finite automata, we have finite amount of memory in the term of states.(

Memory in finite automata is present in the form of states)`Q`

and according to automata principal: any automata can have only finite states. hence finite automata have finite memory, this is the reason the class of automata for regular languages is called finite automata. You can think of a finite automata like a CPU without memory, that has finite register to remember its internal statesFinite State ⇒ Finite Memory ⇒ Only language can be processed for which finite memory needs to store at any instance of time while processing the string ⇒ that language is called Regular Language

Absent of external memory is limitation of finite automate ⇒ or we can say limitation of finite automata defined class of language called Regular Language.

You should read other answer "finiteness of regular language" to learn scope of regular language.

side note::^{n}b^{n}| n > 0 } is subset of`a*b*`

^{n}b^{n}| 10^{>100}n > 0 } is regular, a large set but regular because`n`

is bounded, hence finite automata and regular expression is possible for this language.You should also read:

How to prove a language is regular?