0
$\begingroup$

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

I am purposefully not going though all the steps required to solve the exercise (comment if you need more help).

You might want to have a look at pumping lemma for regular languages .

It gives you a property that all regular languages must satisfy. If you want to show that a language $L$ is not regular, you can show that this property cannot hold. In practice, the proof usually follows these steps:

  • assume towards a contradiction that $L$ is regular
  • choose a suitable word $w \in L$
  • apply the pumping lemma on $w$ to conclude that a new word $w'$ must belong to $L$
  • Use the language definition to show that $w'$ does not belong to $L$ (hence the contradiction).

Hint:

Here is a string $w$ that belongs to your language: $a^n b^n$, for a sufficiently large integer $n>0$.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.