Talen en automaten/2011-12/producten/Lang-e-Tape
Lang-e-tape
Luuk Scholten, Koen Basten
Talen en automaten 2011-12
|
14:40 A |
Beschrijving
Wij hebben zelf een taal gemaakt, deze heet 'Lang-e-tape'.
Deze taal, die in veel opzichten lijkt op BrainFuck, is door onszelf bedacht omdat een geschikte taal waar niet al te veel documentatie over te vinden was moeilijk te vinden was.
Deze taal heeft de mogelijkheden om een aantal bewerkingen op geheugencellen uit te voeren, waarmee het Turing-complete is.
Vanwege het gebruik van haakjes () kan dit programma complexe berekeningen uitvoeren, gegeven dat het geheugen genoeg informatie kan bevatten. Je hebt een oneindig lange tape, en daar wil je berekeningen op uitvoeren, daarvoor kun je onderstaande commando's uitvoeren, je kunt ook de gebruiker om input vragen en zo berekeningen maken op de dingen die gebruiken zegt. Bovendien heeft de taal naast de tape ook een tijdelijk geheugencel, die altijd aangevraagd kan worden. Input wordt op de tape gezet, zo is de tape input en storage tegelijkertijd. Een tape wordt op het eerste moment ingevuld met een oneindige rij van #’en. Hieronder volgt een lijstje met commando's:
| Command | Wat het doet |
|---|---|
| > | Pointer naar rechts. |
| < | Pointer naar links. |
| ^ | Lees waarde van pointercell naar tijdelijke geheugencel. |
| V | Zet waarde van tijdelijke geheugencel, naar de pointercell. |
| ]0[-]255[ | Zet een getal in de geheugencel. |
| * | Output de huidige geheugencel. |
| ' '-'z' | Zet een karakter in de geheugencel. Bijvoorbeeld: ’a’ zet een ‘a’ in de tijdelijke geheugencel.Hierin kan maar één teken worden geplaatst. Meerdere tekens moeten verdeeld worden over meerdere geheugencellen. |
| @ | Vraag om input, de input wordt na de eerstvolgende '#' gezet en die '#' wordt vervangen door een '@', positie van de pointer blijft op de plek waar hij eerst was. |
| $(...) | De huidige waarde van de geheugencel wordt gebruikt hierna wordt de geheugencel op 0 gezet.
Het betekent: Herhaal tot de geheugencel de waarde is die eerst in de geheugencel stond. Een voorbeeld hiervan is: ’@’$(^>) Dit gaat naar de eerstvolgende input waarde. |
| + | Tel het getal van de pointer en het getal van de geheugencel bij elkaar op, als hier een ascii teken staat, gebeurt er niks. |
| - |
Trek het getal van de pointer van het getal van de geheugencel af, als hier een ascii teken staat, gebeurt er niks. |
| !+ | Integer in geheugencel verhogen met 1, doet niks als je een ascii karakter in de geheugencel hebt staan. |
| !- | Integer in geheugencel verlagen met 1, doet niks als je een ascii karakter in de geheugencel hebt staan. |
Een programma termineert zodra alles geparseerd is en er niks meer is om te doen. Dit hoeft niet te betekenen dat de tape of het geheugen leeg is. Op het moment dat de laatste instructie uitgevoerd is, termineert het, verder gebeurt er niks. Mocht het zo zijn dat de laatste instructie een output-instructie is (*), dan is dat het einde van het programma.
Een 'Hello World!' programma ziet er dus als volgt uit:
'H'*'e'*'l'*'l'*'o'*' '*'W'*'o'*'r'*'l'*'d'*'!'*
Een programma om 2 inputs op te tellen zou zijn:
@@>^>>+*
Regulier?
Deze taal is niet-regulier, vanwege de haakjes () die het programma bevat. Zoals al enkele malen bewezen tijdens de college wijst dit op niet-regulariteit, omdat het aantal haakjes bijgehouden moet kunnen worden om regulariteit aan te kunnen tonen. Dit geldt echter alleen als meerdere haakjes binnen elkaar kunnen voorkomen, en niet als elk haakje eerst gesloten moet worden voordat een nieuw haakje geopend mag worden. Dit is echter, zoals bij veel (bijna alle!) programmeertalen, bijna nooit het geval. SQL heeft met zijn subqueries de mogelijkheid hiervoor, en C++ zou niks zijn zonder enkele lagen diep te kunnen nesten.
Een formeler bewijs:
Om te laten zien dat deze taal L niet regulier is, gaan we het pomplemma toepassen.
We gaan nemen aan dat de taal L wel regulier is.
Dan is er een deterministische eindige automaat met k states.
We kiezen voor 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 = \{\$(\} ^k)^k}
Het pomplemma impliceert dat z opgedeeld kan worden in substrings 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 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 v \neq \lambda}
, 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 uv^iw \in L }
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 i \geq 0}
.
Het pomplemma zegt dat v gepompt kan worden.
v bevat de string $(
Zodra dit gepompt wordt bevat de het woord meer begintekens dan eindtekens, daardoor 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 \notin L}
.
Het pomplemma geldt dus niet, dit is tegenspraak, dus we hebben bewezen dat L niet regulier is.
Contextvrij?
Onderstaand is onze weergave van de PDA van onze taal. Op het eerste gezicht waren we ervan overtuigd dat deze taal makkelijk weer te geven was, waarna bleek dat de limiet van 255 voor een integer iets lastiger was om een automaat voor te bouwen. Na wat puzzelen bleek dat we één voor één het rijtje getallen af moesten gaan, van links naar rechts, op dezelfde manier als het in het programma staat. Bijvoorbeeld: als er een 1 aan het begin van de reeks staat, kan dit betekenen dat het 1, 10-19 of 100-199 is. Hetzelfde geldt voor 2-9 en 0. Hierdoor loopt het programma tegen een fout aan als een waarde groter dan 255 wordt ingevoerd.
Alle niet-vermelde stackacties zijn λ / λ , deze hebben we weggelaten omdat het anders te druk werd in de tekening.
De enige beginstate is q0, waarna begonnen wordt met het controleren op correctheid van het programma.
De enige eindstate is ook q0, die alleen bereikt kan worden als het programma leeg is, geen fouten bevat en alle loops correct zijn afgesloten.
Over de getallen nog enige uitleg:
q3 -> q4 accepteert alle getallen in de vorm van 0-255 q3 -> q9 -> q4 accepteert alle getallen 10-99 q3 -> q6 -> q5 -> q4 accepteert alle getallen 100-199 q3 -> q7 -> q5 -> q4 accepteert alle getallen 200-249 q3 -> q1 -> q8 -> q4 accepteert alle getallen 250-255
Deze automaat klopt omdat de enige loop die erin voorkomt ( $( en ) ) een A op de stack pusht. Het programma kan niet termineren zonder dat deze stack leeg is, wat gedaan wordt door de loop af te sluiten met ). Hierdoor kun je een loop in een loop krijgen, omdat de stack dan gewoon groter wordt. Het incrementen en decrementen van getallen gebeurt in twee karakters, namelijk ! als 'begin' van een rekenkundige actie, gevolgd door + of - die aangeven welke actie er gedaan moet worden. Omdat dit twee karakters zijn, is een aparte state nodig. Deze controleert op de aanwezigheid van een + danwel een -, en voert niet uit als deze niet voorkomt. Ook de karakters hebben 2 extra states nodig, om het met een ' te laten beginnen, dan 1 karakter die erin verschijnt, en ' om het te laten beëindigen. De rest van de commando's heeft geen speciale benodigdheden dus daarvoor is geen extra state nodig. Zodra de stack leeg is kan de automaat termineren en is q0 voldoende.
Onderstaand is de grammatica die bij deze taal hoort. De beginstate is opgedeeld in de loop, de getallen, de strings, de overige bewerkingen en lambda. Dit is de representatie zoals deze ook in de PDA omschreven is.
S -> $(S) | ]G[S | QS | 'T'S | λ T -> [a-zA-Z] | T | λ G -> [0-9] | [1-9]A | 1B | 1C A -> [0-9] B -> [0-9]A C -> [1-4]A | 5[0-5] Q -> > | < | ^ | V | * | @ | + | - | !+ | !-
Er is een PDA en een grammatica voor, dus de taal is contextvrij.
