$(6$ points$)$

Let the following pushdown automaton $K=(\{s_0,s_1\},\{a,b\},\{A,B,$#$\},,s_0,$#$)$ be given, where the

transition function is defined as follows:

$(s_0,a,$#$)=\{(s_0,A$#$)\}$

$(s_0,a,A)=\{(s_0,AA)\}$

$(s_0,b,$#$)=\frac{O}{?}$

$(s_0,b,A)=\frac{O}{?}$

$(s_0,,$#$)=\{(s_1,$#$)\}$

$(s_0,,A)=\{(s_1,A)\}$

$(s_1,a,$#$)=\frac{O}{?}$

$(s_1,a,A)=\frac{O}{?}$

$(s_1,b,$#$)=\frac{O}{?}$

$(s_1,b,A)=\{(s_1,)\}$

$(s_1,,$#$)=\{(s_1,)\}$

$(s_1,,A)=\{(s_1,)\}$

$($a$)$ Simulate the pushdown automaton on the two words aab and abb. Write down all reachable

configurations $($including dead$-$ends$)$ and the transitions between them as a tree, i$.$e$.$ your solution

should begin like this:

$($Note: In case of non$-$determinism, there can be more than one configuration reachable from a

single configuration.$)$

$($b$)$ Does the pushdown automaton accept the words aab and abb $?($For this you can refer to your

answer to subtask $($a$).)$

$($c$)$ Give the language of the pushdown automaton $K$ from above. Justify your answer! In particular,

explain how A$\text{'}$s end up on the stack $($what has to be read and when?$)$ and what has to happen

for an $A$ to disappear from the stack again.