Talen en automaten/2011-12/producten/Ook!

Ook!

David van Oorsouw, Tim Janssen

Talen en automaten 2011-12

15:00 A

David van Oorsouw Bachelor Informatica  e-mail  cursuspagina

Bestand:David van Oorsouw.jpg

Tim Janssen Informatica  e-mail  cursuspagina

Beschrijving

Heb je ooit het gevoel gehad dat je het liefst zoals een aap op je toetsenbord had willen rammen. Daar biedt Ook! je een uitkomst. "Ook!" is een Turing-volledige esthetische programmeertaal, ontworpen door David Morgan-Mar. De taal is gebaseerd op de manier waarop Orang-oetangs zouden programmeren (als ze zouden programmeren) en bestaat uit drie simpele syntax-elementen:

• Ook.
• Ook!
• Ook?

Deze kunnen worden gecombineerd tot 8 statements (zie hieronder). Ook! werkt op precies dezelfde wijze als brainfuck behalve dat de tekens vervangen zijn door een combinatie van de woorden van een orang-oetang (Ook). Ook! wordt daarom ook wel een dialect van brainfuck genoemd, omdat Ook! Turing-volledig is heeft het dus als het ware een oneindige band (als invoer) en een lees/schrijfkop. Hieronder een volgt een beschrijving van de taal en een vergelijking met brainfuck:

Ook! Statements

Brainfuck	Ook!	Beschrijving
>	Ook. Ook?	De kop gaat één stap naar rechts
<	Ook? Ook.	De kop gaat één stap naar links
+	Ook. Ook.	Verhoogt de waarde van de byte op de huidige koppositie met 1
-	Ook! Ook!	Verlaagd de waarde van de byte op de huidige koppositie met 1
.	Ook! Ook.	Output de waarde van de byte op de huidige koppositie
,	Ook. Ook!	Input ASCII-byte om de byte op de huidige koppositie deze waarde te geven
[	Ook! Ook?	beweeg je kop naar recht tot de volgende "Ook? Ook!" (]) als de waarde onder de kop 0 is
]	Ook? Ook!	Beweeg de kop naar links tot de "Ook! Ook?" ([)

Een "Hello World"- programma zou er in Ook! als volgt uitzien:

Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook! Ook. Ook! Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook! Ook. Ook. Ook? Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook.
Ook? Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook.
Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook. Ook. Ook. Ook. Ook. Ook. Ook. Ook! Ook. Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook.
Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook! Ook!
Ook! Ook! Ook! Ook! Ook! Ook.

Regulier?

We verwachten dat Ook! niet regulier is, dit omdat er een afhankelijkheid is tussen de statements "Ook? Ook!" en "Ook! Ook?". Om dit nu daadwerkelijk te bevestigen gaan we gebruik maken van het pomplemma. Het bewijs zal een bewijs zijn vanuit het ongerijmde.

Te bewijzen Ook! is niet regulier
Bewijs : Neem aan dat Ook! wel regulier is

Dan is er een DFA m zodat Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle L =\ L(m)}

zeg m heeft k toestanden

Bekijk z = Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle (Ook! Ook?)^k\ (Ook? Ook!)^k }

Dan Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle lengte(z) >\ k}

Dus: z is pompbaar

zeg Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z =\ uvw} met Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle lengte(uv)\geqq k} en Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle uv^iw \in L}

Maar Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle z = (Ook! Ook?)^p\ (Ook! Ook?)^q\ (Ook! Ook?)^{k-p-q}\ (Ook? Ook!)^k}

en Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle uv^2w = (Ook! Ook?)^p\ (Ook! Ook?)^{2q}\ (Ook! Ook?)^{k-p-q}\ (Ook? Ook!)^k \notin L}

want Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \#(Ook! Ook?)=\ k+q \text{ en } \#(Ook? Ook!) =\ k}

dus Parsen mislukt (MathML met SVG- of PNG-terugval (aanbevolen voor moderne browsers en toegankelijkheidshulpmiddelen): Ongeldig antwoord ("Math extension cannot connect to Restbase.") van server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \#(Ook! Ook?) \neq \#(Ook? Ook!)}

Ook! is dus niet regulier

Contextvrij?

Ook! is een contextvrije taal, om dit te bewijzen moeten we een PDA maken of een grammatica opstellen. Wij hebben ervoor gekozen om een grammatica te maken voor Ook!, omdat dit ons het makkelijkste leek. Hieronder zie je een mogelijke constructie van de grammatica van Ook!.

S --> ABS | ACS | AAS | BBS | BAS | BCS | CAS | CBS | λ
A --> "Ook."
B --> "Ook!"
C --> "Ook?"