Stelling : Als twee staten niet onderscheidbaar zijn door het table-filling algoritme, dan zijn ze equivalent.
kan er iemand mij da bewijs is uitleggen
wtf is da met die "korter dan de string die een slecht paar identificeerd :s
[TA] theorema 4.20
Moderator: Praesidium
Oeioeioei, das moeilijk informeel uit te leggen, even nadenken he.
Zie, gebt een automaat, dat geminimalizeerd is. En stel nu dat er minstens 2 onderscheidbare staten zijn. Laten we nu twee staten uitkiezen, die onderscheidbaar zijn en die het kortste pad (in de automaat) van de eindstaat in kwestie af liggen. Bijvoorbeeld we hebben q0 en q5, en bij het volgen van 01 komt q0 uit in q2, wat een eindstaat is, en q5 komt na 01 uit in q7, wat geen eindstaat is, stel nu dat 01 de kortste onderscheidbare afstand is.
Maar, na het evalueren van het eerste teken, de 0, kom je in bijvoorbeeld q1 en q6 uit, nu als ge vanuit q1 een 1-transitie maakt, komt ge in q2 terecht, een eindstaat, en als ge in q6 een 1-transitie maakt, komt ge in q7 terecht, dus deze zijn ook onderscheidbaar. Maar .. was er nu ni gezegd da q0 en q5 de kortste bad-pairs waren ?? En q1 en q6 zijn ook bad pairs, en deze zijn korter ??
Dit is een contradictie, dus de stelling geldt niet, en het automaat is geminimaliseerd.
Okee ik weet daget nog vaag klinkt, tis nog een vaag bewijs en kvin zelfs daze ni klopt, maar dit is de beste manier om het te onthouden.
Zie, gebt een automaat, dat geminimalizeerd is. En stel nu dat er minstens 2 onderscheidbare staten zijn. Laten we nu twee staten uitkiezen, die onderscheidbaar zijn en die het kortste pad (in de automaat) van de eindstaat in kwestie af liggen. Bijvoorbeeld we hebben q0 en q5, en bij het volgen van 01 komt q0 uit in q2, wat een eindstaat is, en q5 komt na 01 uit in q7, wat geen eindstaat is, stel nu dat 01 de kortste onderscheidbare afstand is.
Maar, na het evalueren van het eerste teken, de 0, kom je in bijvoorbeeld q1 en q6 uit, nu als ge vanuit q1 een 1-transitie maakt, komt ge in q2 terecht, een eindstaat, en als ge in q6 een 1-transitie maakt, komt ge in q7 terecht, dus deze zijn ook onderscheidbaar. Maar .. was er nu ni gezegd da q0 en q5 de kortste bad-pairs waren ?? En q1 en q6 zijn ook bad pairs, en deze zijn korter ??
Dit is een contradictie, dus de stelling geldt niet, en het automaat is geminimaliseerd.
Okee ik weet daget nog vaag klinkt, tis nog een vaag bewijs en kvin zelfs daze ni klopt, maar dit is de beste manier om het te onthouden.
Who is online
Users browsing this forum: No registered users and 9 guests