is a*b* is a regular expression ?

Question

if yes then what is the difference b/w a*b* and a^n b^n ?if yes what is that ? if nothing then why a^n b^n is not a regular Language ?

Forgive me if this is a stupid question .But as a non cs student i don't know what is going on in TOC .

Answer 1

Yes a*b* -- Regular one ( It can take any number of a and b ) 

aⁿbⁿ ---- An equal no of a and equal no of b 

The regular lang is accepted By a Finite state Automata . It doesnt have any memory with it .

So for the first one it doesnt have any restriction to keep track how much a and how much b it has read . it wouldnt  have restriction of a, b, aaabbbbbb, abbbb,bbbbb , aabb etc 

While for the second , if it has read 3 a then it should read 3 b also , but FA doesnt have memory only , it read 3 a and then when it start reading b , it doesnt have any idea about how much a it read . 

Hence the second one is non regular :)

I hope it help you ! 

Comments

Thanks.

---

welcome :)

Answer 2

 a*b* = write any no. of a and any no. of b without any condition.  ( so we can design finite automata for this which take 2 state , when we able to make FA then these language are Regular)

ex:  a^m bⁿ  here m and n are diffrent variable so we have no restriction of no. of a and no. of b are equal , less than , greater than etc.

 aⁿ bⁿ = always as no. of a equal to no. of b.. so we cannot create FA for it. B/C comparision is present b/w a and b. ( when comparission present then not regular ) ex. aⁿ bⁿ cⁿ here comparision present among a,b,c. always equal no. of a,b,c.