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 ?
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP