dfa - How can I prove if this language is regular or not? -

how can prove if language regular or not?

l = {aⁿ bⁿ: n≥1} union {aⁿ bⁿ⁺²: n≥1}

i'll give approach , sketch of prove, there might holes in believe can fill yourself.

the idea use nerode's theorem - show there infinte number of equivalence groups r_l - , theorem can derive language irregular.

define 2 types of sets:

1. g_j = {aⁿb ^k | n-k = j , k≥1} each j in [-2,-1,0,1,...]
2. h_j = {a^j } each j in [0,1,...]
3. g_illegal = {0,1}^* / (g_j u h_j) [for each j in specified range]

it easy see each x in g_illegal, , each z in {a,b}^*: xz not in l.

so, every x,y in g_illegal , each z in {a,b}^*: xz in l <-> yz in l.

also, each z in {a,b}^* - , each x,y in g_j [same j both]:

• if z contains a, both xz , yz not in l
• if z = b^j, xz = aⁿ b^k b^j, , since k+j = n - xz in l. same applies y, yz in l.
• if z = b^j+2, xz = aⁿ b^k b^j+2, , since k+j+2 = n+2 - xz in l. same applies y, yz in l.
• otherwise, x bⁱ such i≠j , i≠j+2, , both xz , yz not in l.

so, every j , every x,y in g_j , each z in {a,b}^*: xz in l <-> yz in l.

prove same every h_j using same approach.

also, easy show each x g_j u h_j, , each y in g_illegal - z = b^j, xz in l , yz not in l.
for x in g_j, , y in h_i, z = ab^j+1 - easy see xz not in l , yz in l.
it easy see x,y in g_j , g_i respectively or x, y in h_j, h_i - z = b^j: xz in l while yz not.

we proved sets created equivalence relations r_l nerode's theorem, , since have infinite number of these sets, each equivalence relation r_l [we have h_j , g_j every j] - we can derive nerode's theorem language l irregular.