0
$\begingroup$

After working through some examples of proving the non-regularity of languages I encountered this language

$$ L = \{(ab)^{i}a^{j} | i \geq j, i,j \in \mathbb{N}\} $$

Where $a^{k}$ = a repeated k times. Is this language regular? I believe not since there are infinitely many strings $(01)^{i}$ with $i \geq j$, so a DFA or NFA cannot accept the language

$\endgroup$
3
$\begingroup$

A regular language can be recognised by a finite state machine.

After processing (ab)^i and (ab)^i’, i ≠ i', the state machine must be in different states: If say i < i’, and j = i’, then (ab)^i a^j is not in the language, but (ab)^i’ a^j is, so processing a^j from both states must end in different states, one not accepting, one accepting.

Since i, i’ were arbitrary there cannot be a finite number of states.

$\endgroup$

Your Answer

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