1

If $L = \{a^nb^n, n \leq 100\}$ is regular, is $L_2 = \{a^nb^n, n > 100\}$ also regular?

$L$ is regular because we can draw an FA(finite automata) for it. It's not possible to draw an FA for $L_2$, right?

alkabary
  • 6,214
stevetronix
  • 433

1 Answers1

2

The language $L_1$ is regular since it's finite. The language $L_1 \cup L_2 = \{a^n b^n : n \geq 0\}$ is classically not regular. If $L_2$ were regular then so would $L_1 \cup L_2$ be (why?), so $L_2$ cannot be regular.

Yuval Filmus
  • 57,157