Tentamen (uitwerkingen)
COS3701 Assignment 2 Yearly Module 2022 (Unique Number: 830417)
- Vak
- Instelling
COS3701 Assignment 2 Yearly Module 2022
[Meer zien]Voorbeeld 3 van de 17 pagina's
Voorbeeld 3 van de 17 pagina's
In winkelwagen
In winkelwagen
gesponsord bericht van onze partner
Verkoper
Volgen
t0dd
Ontvangen beoordelingen
Voorbeeld van de inhoud
UnisaAssignHelpCOS3701
Assignment 2
Unique Number:
830417
, UnisaAssignHelp
Question 1
Build a DPDA to show that the language L = {(ab)naaa(ba)n−2 | n > 2} is deterministic context free.
The smallest word in this language is when n = 3. This word is abababaaaba. All words in this language start
with three or more abs and end with one or more bas where there are always two more abs than bas.
The trick to showing that this language is context free is to use the PDA to “match” the occurrences of ab
to the occurrences of ba which appear later in the string. We should also take care of the fact that there
have to be two more abs than bas but there has to be at least one ba (and three abs).
The aaa string in the middle is a separator and does not affect the decision of whether or not the language
is context free.
Our PDA can thus be outlined as
1. Read three instances of ab (but do nothing to the stack). These are the leading abs that we can simply
get rid of because we know there should be exactly three of them.
2. Read in any other instances of ab and for each such instance push an X onto the stack. Here we are
essentially counting how many abs we have.
3. Read in aaa (but do nothing to the stack)
4. Read in instances of ba and for each instance pop an X off the stack. Here each ba is ticked off against
an ab that was read at the beginning of the string.
5. When a ∆ is popped from the stack then we know we have just read the ba that matches the three
abs that must be at the start of every string.
6. When the stack is empty then the DPDA must check that all of the bas have been read (ie there is no
additional input).
We can now build a PDA to do this.
The PDA is shown in Figure 1.
2
, UnisaAssignHelp
Figure 1: A DPDA to recognise L = {(ab)naaa(ba)n−2 | n > 2}
The six phases outlined above can be seen quite easily in the layout of the PDA.
3
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper t0dd. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,36. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 83614 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen
Laatst bekeken door jou
