Talen en automaten/2011-12/producten/NXT

definitive

NXC

Vincent Slieker, Fleur de Visscher

Talen en automaten 2011-12

14:40 B

Vincent Slieker Bachelor kunstmatige intelligentie  e-mail  cursuspagina

Fleur de Visscher Bachelor kunstmatige intelligentie  e-mail  cursuspagina

Description

NXC stands for "Not eXactly C" and is a programming language made for the Lego Mindstorms NXT series. NXT is a Lego series that enables you build a robot with the use of Lego bricks and Lego motors. The Lego motors can be control by programming a behavior for the motors in NXC . The NXC language was created by John Hansen and is as the name "Not eXactly C" already suggest derives it’s syntax for large parts from the programming language C. The Syntax from C and NXC have a lot in common but there are important differences, mainly because NXC focuses on making the language practically usable for people with little or no programming experience. Some of the aspects of the NXC code will be explain below because they will be used in explaining why NXC is a non-Regular and Context Free language.

NXC works amongst other things with tasks, subroutines, inline functions and macros that enable a user for example to control multiple Lego motors at the same time without having to know the basics about creating parallel processes. A tasks normally run parallel to each other and takes care of different things that may have to be done at the same moment. Inline functions are functions that replace pieces of code that can be used in many different places and in different tasks, they cost however memory that is limited with Lego constructions. Subroutines can be used when pieces of code must be used at different places but in the same task, they have the advantage of requiring less memory than Inline functions. Finally macros are useful for small pieces of code that must be used a different places throughout the program.

The most general form of a working NXC program is:

 task main()
 {
 statement1;
 statement2;
 …
 }

Where a statement is of the form:

statement	arguments
OnFwd(o, x);	o ∈{OUT_X} ,x ∈ N
Wait(x);	x ∈ N
Off(o);	o ∈{OUT_X};
move_time = Random(x);	x ∈ N
turn_time = Random(x);	x ∈ N
SENSOR_i == x);	x, i ∈ N
bool something = b;	b ∈ {false, true};
Stop (b);	b ∈ {false, true};
...	...

Controlling the Lego motors is made simple by using 'giving' functions as demonstrated in the example code given below :

task main() //sets a new task. main() is compulsory
{   
OnFwd(OUT_BC,75); //ask the motors connected to ports B and C to move forward at a power of 75. 
Wait(5000); //wait for 5 seconds (note that 1000 = 1 second)  
Off(OUT_BC); //off the motors connected to ports B and C
}>

Regular?

Through the Pumping lemma we want to prove the non-regularaty of NXC.

According to the NXC tutorial : "There is now one repeat statement inside the other. We call this a “nested” repeat statement. You can nest repeat statements as much as you like. Take a careful look at the brackets and the indentation used in the program .... the brackets always come in pairs."

an example of "nested" repeat is:

task main() { repeat(x) { repeat(y) { statement1; statement2; … } } Off(z); }

since we are interested in the repeat statement, we abstract the 'main' outside and the 'statements' inside the loop.

More general one would get a program of the form: 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 (repeat \{ \ )^k \ \}^k.}

according to the pumping lemma we need to find a Z such that:

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 \ and \ length(Z) <= k }

we choose 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 = (repeat \{ \ )^k \ \}^k \ where \ k=p+q }

with:

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= (repeat \{ \ )^p }

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= (repeat \{ \ )^q }

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= \ \}^{p+q} }

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 = (repeat \{ \ )^p \ (repeat \{ \ )^q \ \}^{p+q} }

Every 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 ' = uv^iw } must also be accepted

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 if \ i=2 \ , \ Z ' = uv^2w }

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' = (repeat \{ \ )^p \ (repeat \{ \ )^{2q} \ \}^{p+q} \ = \ (repeat \{ \ )^{p + 2q} \ \}^{p+q} }

now Z' has 2q more repeat statements as closing brackets and therefore will not be accepted by NXC, hence NXC is not regular.

Context-free?

In order to show that NXC is a context-free grammar we will show that the grammar of this language can be written in the form S -> w where S is a single nonterminal symbol and w is an empty string or a string consisting of terminals and/or nonterminials . Because NXC is an language that consist of many possible statements and rules we abstract from arguments and constants of the functions, statements and loops in order to limit the domain that needs to be specified.

In the grammar below, we used the following abbreviations:

• s ∈ {s₁, s₂, s₃,..., s_n} where s_i is one of the many statements as describe above.
• r = repeat
• w =while
• i = if
• u = until
• e = els
• ei = elsif
• dw = doWhile
• f = for

We will assume that the functions above are context-free in itself and show that function body’s they may possess are always context-free. As show below these functions can be used according to the definition of an context-free grammar, hence proving that this domain of our this language is context-free.

Let G be the context-free grammar for NXC:

G = ( V, ∑, P, S)

V = ( S, C, B, A, T, L ,R)

∑ = { Macro, Task, Sub, Inline, s, r, w, i, u, e, ei, dw, f, {, }, λ }

P:

 S → Macro S
 
 C → Task L B R C | Sub L B R C | Inline L B R C
 
 B → A L T B R | λ
 
 A → r | w | i | u | e | ei | dw | f 
 
 T → s T | s | λ
 
 L → {
 
 R → }