0
$\begingroup$

I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?

$\endgroup$
4
  • 1
    $\begingroup$ So, what is your question? What did you try (in details)? Where did you get stuck? These should be included in the the OP. $\endgroup$
    – fade2black
    Oct 23 '17 at 0:13
  • $\begingroup$ so far i tried using the adversary pumping lemma, let adv pick n and we pick z = $a^{100}a^nba^n(a^nba^n)^r$ im not sure if my setup is correct. $\endgroup$
    – Jenny
    Oct 23 '17 at 3:54
  • 1
    $\begingroup$ Possible duplicate of How to prove that a language is not regular? $\endgroup$
    – quicksort
    Oct 23 '17 at 4:48
  • 1
    $\begingroup$ Get rid of the initial part $a^{100}$ by taking an appropriate quotient. $\endgroup$ Oct 24 '17 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.