These two are equivalent expressions.If you construct FA for the LHS ,then the same FA can also be used for RHS or vice versa. So two machines are equivalent iff languages generated by them are same.I dont know other way to proof this:(

The Gateway to Computer Science Excellence

+2 votes

**(a*b*)* = (a + b)***

I always used this while solving questions. It seems correct also because when ever I pick a random string over {a, b} then I found that it can be generated from (a*b*)*. But I don't have any formal proof for this.

Someone, please proof this.

0

These two are equivalent expressions.If you construct FA for the LHS ,then the same FA can also be used for RHS or vice versa. So two machines are equivalent iff languages generated by them are same.I dont know other way to proof this:(

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,364 answers

198,492 comments

105,260 users