# Constructing a minimal pushdown automaton for counting characters in substrings

I have to construct a pushdown automaton for the following language over alphabet {a,b,c}:

## L={ ucv | |u|!=|v|; u,v={a,b}* }

(note: u,v are substrings over alphabet {a,b}, |u| is length of substring u)

My tutor has constructed a PDA using 4 states, however - I believe it's possible to construct this with only 3. Here's what I came up with:

Legend: QO = initial state, QF = final/accepting state. Directed edges are named after transitions in the following form

input_character, highest_element_in_stack | new_highest_element(s)_in_stack


The basic idea behind it is:

QO counts the number of characters in substring u by pushing x's.

Q1 counts the number of characters in substring v by popping x's.

Is my PDA correct or is it missing something crucial that I haven't noticed?