For a given language
$a^{n}b^{n}w | n \geqslant 0, w\epsilon \left \{ c,d \right \}^{*}$
We can't have Push Down Automata. This is because, we cannot maintain (push to stack) count for $a$'s and decrement (pop from stack) count when we see $b$'s in input. Since the stack would be empty after seeing last $b$ of $b^{n}$, so $w$ cannot be checked for validity (i.e has $n$ length).
Your opinion of
- pushing $2$ $a$'s for every $a$ you see on input
- and popping single $a$ for every $b$ you see in $b^{n}$
- and popping single $a$ for each character you see on $w$
would not work for few cases.
For example:
Consider a string
$aaabbccdd$
On seeing $a$, I will put two $a$'s on stack. So when I have read $aaa$, stack will look like below
On seeing $b$, I will pop single $a$ from stack. So when I have read $aaabbb$, stack would look as below
Now, on seeing every character of $w$, I will pop single $a$. So after I have read complete input $aaabbccdd$, stack would be empty.
But the string $aaabbccdd$ is not a valid string in the language. Number of $a$'s are not equal to number of $b$'s
