TransWikia.com

Is it possible to prove $a^{5n}b^{3m}c^{n}d^{m}$ is irregular knowing $a^nb^n$ is irregular?

Mathematics Asked by Parsa Noori on February 3, 2021

The proof using the pumping lemma is super easy but is it possible to solve it without pumping lemma and knowing $a^nb^n$ is irregular ?

One Answer

we can use homomorphism to solve problem. Define h(L) : h(a) = a h(b) = a h(c) = bbbbb h(d) = bbb

h(L) = a^(5n)a^(3m) (bbbbb)^n(bbb)^m = a^(5n)a^(3m) b^(5n)b^(3m) = a^(5n+3m) b^(5n+3m)

Define C = 5n+3m ----> h(L) = a^C b^C Then we can show that a^C b^C is irregular with pumping lemma. Or show a^C b^C is irregular with pigeonhole principle easily. If h(L) is irregular, L is irregular too. So we solve the problem :)

Answered by Faeze Sarlakifar on February 3, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP