Talen en automaten/2011-12/producten/Whitespace

Uit Werkplaats
Ga naar: navigatie, zoeken
Page Break




Algolfrag.jpg

Talen en automaten

Erik Barendsen

 © comments



Whitespace

Maaike ter Borg, Vilas Pultoo



Talen en automaten 2011-12



15:20 B






Maaike ter Borg Bachelor kunstmatige intelligentie
 e-mail 

cursuspagina

Bestand:Maaike ter Borg.jpg

Vilas Pultoo Bachelor Informatica
 e-mail 

cursuspagina

Bestand:Vilas Pultoo.jpg
Page Break





Beschrijving

Whitespace is een esoterische programmeertaal die alleen gebruik maakt van spaties, tabs en enters. Alle andere tekens worden niet geaccepteerd en kunnen dus gebruikt worden voor commentaar[1]. Het idee ontstond tijdens een gesprek tussen een aantal geeks in een bar in 2002. Edwin Brady en Chris Morris maakten de taal in 2003 en maakten deze openbaar op 1 april 2003. Dit was volgens de makers puur toeval hoewel het wel voor veel extra aandacht heeft gezorgd. Er is een werkende compiler gemaakt voor Whitespace en het is mogelijk om eigen programma's te maken. De taal is voor mensen wel bijzonder onpraktisch omdat er slechts 3 tekens worden gebruikt om mee te programmeren en ze zijn allemaal onzichtbaar. De makers zelf geven als handige toepassing dat spionnen het kunnen gebruiken en vervolgens te printen, zo kan niemand meer zien wat er stond. Helaas geldt dit dus ook voor de spion zelf!

Hieronder een voorbeeld[2] van een Whitespace programma, waarin de tekens spatie en tab ieder een eigen kleur hebben voor de duidelijkheid. LF's worden weergegeven als nieuwe regels.

Rood = Spatie

Groen = Tab


Whitespace voorbeeld.png

Regulier?

Om te kijken of Whitespace een reguliere taal is of niet gaan we gebruik maken van het pomplemma. Als Whitespace een reguliere taal is zou de taal geaccepteerd moeten worden door een deterministische eindige automaat met k toestanden.

Volgens het pomplemma heeft een reguliere taal 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} de eigenschap dat een willekeurig woord 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} uit 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} met lengte(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} ) ≤ 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} opgedeeld kan worden in 3 delen; 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 u} ,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 v} 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 w} . Deze 3 delen voldoen aan de volgende eisen:

  • lengte(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} ) ≤ 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}
  • lengte(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 v} ) > 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 0} .

Als ze aan deze eisen voldoen moet het woord 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} met voor elke 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 i} ≥ 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 0} ook in de taal 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} zitten.

Het woord 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} , die aan al deze eisen voldoet is: Tab Tab Tab LF (S S)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} LF LF LF

  • 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 u} = Tab Tab Tab
  • 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 v} = LF
  • 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 w} = (S S)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} LF LF LF

Dit woord zit in de taal 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} , lengte(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} ) > 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} , lengte(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} ) < 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} en lengte(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 v} ) > 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 0} . Nu gaan we dit woord proberen te pompen, waarbij v dus herhaald gaat worden. Dit moet gelden voor elk aantal v's. 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} = Tab Tab Tab LF LF ( S S )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} LF LF LF. Deze combinatie van elementen komt echter niet voor in de taal (zie ook de contextvrije grammatica). Hierdoor hebben we dus bewezen dat Whitespace geen reguliere taal is.

Contextvrij?

Als er een contextvrije grammatica bestaat voor Whitespace is de taal contextvrij. Om een dergelijke grammatica te maken hebben we gebruik gemaakt van de tutorial pagina van Whitespace [3]. Er zijn maar 3 soorten elementen in het alfabet; namelijk 'Tab' 'Space' en 'LF'. Ook is het mogelijk om een leeg programma te hebben. In de tutorial komt naar voren dat er 5 begintoestanden zijn om een commando te maken, namelijk:

  • Space
  • Tab Space
  • Tab Tab
  • LF
  • Tab LF

Vandaar dat wij S naar deze 5 begintoestanden laten gaan. Voor elk van deze 5 begintoestanden is in de tutorial vastgesteld wat daarna mag komen. Vandaar dat achter elk van deze 5 begintoestanden een andere variabele dan S staat (A,B,C,D en E). Bij al deze variabelen geven we alle mogelijkheden die na de begintoestand mogelijk zijn. Als voorbeeld: als de begintoestand Tab Tab was, mag er daarna alleen een Space of een Tab komen. Dus in C zijn dit de enige 2 mogelijkheden. Vanuit deze 5 variabelen kunnen we op 1 toestand na(LFLFLF) altijd weer terugkeren naar S, omdat na ieder afgesloten stukje je weer kunt beginnen aan een nieuw stukje. Echter LFLFLF is een eindtoestand, dus na begintoestand 'LF' en daarna nog 2x 'LF', eindigt dit het programma. Na deze toestand ga je dus niet terug naar S.

Door deze stappen zijn we uiteindelijk op de volgende grammatica gekomen:

G = ( V, ∑, P, S)

V = ( S, A, B, C, D, E)

∑ = (Tab, Space, LF)

P = 

S → Space A | Tab Space B | Tab Tab C | LF D | Tab LF E

A → Space S | LF Space S | Tab Space S | LF Tab S | LF LF S| Tab LF S

B → Space Space S | Space Tab S | Space LF S | Tab Space S | Tab Tab S

C → Space S | Tab S

D → Space Space S | Space Tab S | Space LF S | Tab Space S | Tab Tab S | Tab LF S | LF LF

E → Space Space S | Space Tab S | Tab Space S | Tab Tab S

Bronnen

  1. ↑ "Whitespace"
  2. ↑ "Plaatje Whitespace"
  3. ↑ "Whitespace tutorial"
Overgenomen van "https://lab.cs.ru.nl/algemeen/index.php?title=Talen_en_automaten/2011-12/producten/Whitespace&oldid=177236"