Talen en automaten/2011-12/producten/Cow
| busy |
Beschrijving van de taal Cow:
Gerhard Klassen, Tobias Schröter
Talen en automaten 2011-12
|
13:55 B |
 |
Description
Cow is an esoteric programming language which was developed by Sean Heber in 2003. It is a Brainfuck variant with four more instructions(Brainfuck does not have equivalent instructions to: OOO, MMM, OOOM, oom). Alex van Oosterijk and Martijn van Beek proofed that COW is also Turing-Complete. COW works like a Turingmachine. It jumps from one storage "block" to the next. It can read change and write values into the blocks. It is case sensitive and just contains commands which consists of M's and O's. All other character combinations are ignored and treated as comments. COW is meant as a humorous programming language. Nevertheless it is fully functional! Frank Buss also implemented COW in Javascript. That makes it possible for anyone to write COW programs just trough his browser. If you are interested check It out on:Tool.
The following table is showing the commands, their index and their explanation.
| Code | Command | Explanation |
|---|---|---|
| 0 | moo |
This command goes along with the MOO command. If this command is executed and it encounters a MOO comman during a normal execution, it is looking for a matching MOO command in reverse way. While searching, it skips the command which is directly infront of it. |
| 1 | mOo | Moves one block back from the current position. |
| 2 | moO | Moves one block forward from the current position. |
| 3 | mOO | This command treats the value which is in the current memory block like an instruction. 3 – is an invalid command because this would result in a infinite loop. |
| 4 | Moo | Should the current memory block contain a '0', it is treat like a standard ASCII character and is being stored in the current memory block. If the current memory block is not '0' then the corresponding ASCII character will be printed. |
| 5 | MOo | Current Memory block value = Current Memory block value -1 |
| 6 | MoO | Current Memory block value = Current Memory block value +1 |
| 7 | MOO | If the current memory bock contains a 0, this command skips the next command and resumes after the next moo command. If the current memory block value does not contain a '0' it goes on with the next command. |
| 8 | OOO | Set the value of the current memory block to '0' |
| 9 | MMM | If there is a value in the register, this command pastes that value into the current memory block and clears the register. Otherwise it copies the current memory block value. |
| 10 | OOM | This command prints the value of the current memory block to the output as an integer. |
| 11 | oom | Read the input and save it as an integer in the current memory block. |
Regular
An attribute of regular languages is that you can pomp it anywhere, so that it is still accepted, we call this feature pomplemma. To check if COW is regular or not we use this attribute of regular languages to show that COW is not regular. Should the result be, that COW can be pomped, we still would not know if the language is regular or not. Then we still would have to create a machine for a regular expression. We think, that cow is not regular and thats why we try to get a result with the pomplemma. An important attribute of COW is that every “MOO” must be followed by a “moo” because that is the way a while loop is described. Thats why we can say that a accepted program has to look like:
This program has more than “t” signs, thats why there has to be a circle in the first t states. Thats why you could write this program also on another way. For example:
A circle got q signs. According to the pomplemma programs in regular languages are still accepted if you repeat the circle more than once. That means that following rule has to be accepted:
According to the syntax of the program this is not allowed because every MOO must be followed by a moo. This does not work because there are q MOO's which do not have a closing moo. All together we can say that COW is not a regular language because a regular language must be pompable.
Context-free
To proof that a language is context-free, you can create a PDA or a grammar. We have chosen to create a grammar because we think that it is the easiest way in this case.
Our alphabet consists of {moo, mOo, moO, mOO, Moo, Moo, MoO, MOO, OOO, MMM, OOM, oom}. Every letter of the alphabet consists of a compilation of three ‘real’ letters which are capital or small.
NOTE: Usually you use great letters for non-terminals. In our case we got commands with great letters so that we chose to represent states with BOLD letters.
| State | execute |
|---|---|
| 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 S\to} | WS | VS | mooS | MooS | HS | MOO S | OOO S | MMM S | 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 W\to} | MOO S moo |
| 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 H\to} | mOo | moO |
| 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\to} | MOo | MoO |
| 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\to} | OOM | oom |
The grammar is correct because all commands are listed. All commands are reachable from state S. If you create a loop, MOO as the beginning and moo as the end are created. Everything from state S can be placed between the beginning and the end. It also can be lambda. The other commands are independent from each other and can be created randomly.
State V describes the pointer movement (forward and backwards).
State H describes the increment and decrement of the current memory block value. The last State I describes the In- and Output. With the characterization of the language COW with a grammar, we proofed that it is context-free.
