oefening M&B

Forum van 2de Bachelor Informatica.

Moderator: Praesidium

Katleentje
Posts: 49

oefening M&B

Post#1 » Sun Jan 15, 2012 11:26 pm

Wat is de deterministische PDA van {0^n1^m|n>=m}

User avatar
Joachimvdh
Prosenior
Posts: 1092

Re: oefening M&B

Post#2 » Mon Jan 16, 2012 12:21 pm

Het komt neer op:
- een start staat q0: elke keer ge een 0 ziet pusht ge een symbool op de stack.
- een accept staat q1. Daar komt ge in terecht als ge een 1 leest in q0 en er nog een symbool op de stack staat (dat niet bottom of stack symbool is), of een epsilon transitie vanuit q0 (=geen 1'en). In die staat kunt ge nog 1'en lezen die dan elke keer een symbool poppen
- een vuilbak staat: hier komt ge zowel vanuit q0 en q1 in terecht als ge een 1 leest met een bottom of stack symbool als top of stack. Ook als ge in q1 ineens een 0 leest.

Kan zijn dat er hier en daar iets aan rammelt, das echt lang geleden die PDA's :P

(edit: kweet ni of epsilon mag in een deterministische PDA? anders maakt ge gewoon q0 ook een accept staat ofzo)

Return to “2de Bachelor”

Who is online

Users browsing this forum: No registered users and 8 guests