Which one of the following strings is not a member of L(M)?

Concept

A PDA that, in the start state s, pushes one stack symbol for every input symbol, takes a single switch edge to the accepting state f only on reading an 'a' (pushing nothing), and in state f pops one stack symbol per input symbol, accepts exactly the balanced family L(M) = { x a y : x, y ∈ {a, b}*, |x| = |y| } - an odd-length string with an 'a' at its exact centre. Each prefix symbol pushes one, the central 'a' is consumed by the switch, and each suffix symbol pops one, so the pushes |x| must equal the pops |y|.

Applying it to each string

Check each candidate: the centre symbol must be 'a' and the two halves must have equal length.

1. "aaa": length 3, centre symbol 'a'; halves "a" and "a" have equal length 1 = 1, so it is a member.

2. "baaba": length 5, centre symbol 'a'; halves "ba" and "ba" have equal length 2 = 2, so it is a member.

3. "bab": length 3, centre symbol 'a'; halves "b" and "b" have equal length 1 = 1, so it is a member.

4. "aabab": length 5, centre symbol 'b' (not 'a'). The switch edge to the accepting state fires only on an 'a', so it cannot be taken at the balance point, and no split puts an 'a' in the middle with equal-length halves - so it cannot be balanced and is not a member.

Cross-check

Only the string whose middle symbol is 'b' fails the pattern: "aabab" has 'b' at its dead centre, while "aaa", "baaba" and "bab" all have 'a' there.

Hence "aabab" is the string that is not in L(M).