Talen en automaten/2011-12/producten/Brainfuck

Brainfuck

Lars Bade, Moritz Neikes

Talen en automaten 2011-12

13:40 B

Lars Bade Informatica  e-mail  cursuspagina

Moritz Neikes Informatica  e-mail  cursuspagina

Bestand:Moritz Neikes.jpg

Beschrijving

Brainfuck is een minimalistische programmeertaal die 1993 van Urban Müller ontworpen was. Ze omvat maar acht verschillende tekens en is met betrekking tot de werkwijze vergelijkbaar met de Turing-Machine . Dus bestaat er een band van (in de theorie) oneindige lengte waarop een pointer staat die de waarde van een cel kan lezen of veranderen.

Bij de beschrijving van de taal gaan wij uit van de oorspronkelijke publicatie.

De acht tekens en hun betekenis worden in de tabel hieronder beschreven:

Brainfuck commando's

teken	betekenis
>	gaat een stap verder
<	gaat een stap terug
+	verhoogt de waarde om een
-	verlaagt de waarde om een
.	drukt de waarde af
,	slaat een byte data op
[	als de waarde 0 is, wordt alles tot de corresponderende ] overgeslagen
]	als de waarde niet 0 is, wordt de code tussen [ en ] herhaalt

Andere tekens worden van een compiler geïgnoreerd en kunnen dus gebruikt worden om het programma te commenteren.

Brainfuck valt onder de categorie “esthetische programmeertalen” en is door de slechte overzichtelijkheid (waar de naam ook zeker met te maken heeft) vrij onhandig voor complexe programma's. Ook zet Müller weliswaar de grootte van het array vast (naamelijk 30 000 cellen ) maar hij defineerd niet wat er gebeurt als de pointer achter het eind van het tape probeert te lezen. Dit en ander details zijn dus afhankelijk van het dialect.

Regulier?

Om te bewijzen dat Brainfuck geen reguliere taal is maken wij gebruik van het pomping-lemma. We nemen dus aan dat Brainfuck wel regulier is. Dan is de taal ook representeerbaar door een niet-deterministische automaat 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 k} toestanden.

In de beschrijving van de taal (het "README"-bestand binnen de publicatie) wordt duidelijk dat het aantal haakjes gebalanceerd moet zijn. Müller noemt dit "balanced brackets". Dit betekend dat er voor elk 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 precies een 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 ]} moet bestaan en vice versa, anders wordt het programma niet toegelaten. Dus is 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 [^k ]^k } een toegelaten program. Omdat dit program meer 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 k} tekens omvat, moet er ergens een circel in de eerste 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 k} toestanden zitten.

Dus is het programma ook te schrijven als 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 [^p[^q[^{k-p-q}]^k} 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 q > 0 } . Dan bevat de circel 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 q} tekens. Volgens de aanname van het pomplemma is een programma in een reguliere taal ook dan nog steeds toegelaten, als de circel meerdere keer wordt doorlopen. Dus moet ook 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 [^p[^{2q}[^{k-p-q}]^k = [^{k+q}]^k} toegelaten zijn. Maar dit programma bevat blijkbaar geen gebalanceerde aantal haakjes, er zijn naamelijk 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 q} opene haakjes die niet worden gesluiten. Dus wordt dit programma niet toegelaten en dus kan Brainfuck geen reguliere taal zijn.

Contextvrij?

Om te tonen dat Brainfuck een contextvrije taal is, geven we de contextvrije grammatica voor Brainfuck:

S → OS | MS | CS | LS | TS | λ
O → + | -
M → > | <
C → . | ,
L → [S]
T → alle UNICODE-tekens behalve de boven genoemde

De laatste regel laat op elk plek het invoegen van willekeurige UNICODE-tekens toe (behalve + - , . < > [ ] ). Deze tekens hebben geen uitwerking op het programma maar kunnen gebruikt worden om commentaren toe te voegen.

Men kan brainfuck ook door een heel eenvoudige PDA beschrijven:

De enige restrictie in Brainfuck wordt door de haakjes gegeven. In deze PDA wordt voor elk opend haakje een stack-symbool toegevoegt en alleen door een sluitend haakje wordt dit symbool weer eruit gehaalt. Dus moet het aantal haakjes in elk geval gelijk zijn en zonder een opend haakje kan ook nooit een sluitend haakje worden gelezen.