Exercise $35$ Skyline language

The pen of a plotter moves on a grid. If it currently is at a point $p=(x,y)inZZ,$ then it accepts

three different commands: $u($upwards$),d($downwards$)$ and $r($right$).$ The pen will move to the point

$p^{\text{'}}=(x,y+1),(x,y-1)$ or $(x+1,y)$ respectively and draws a line from $p$ to $p^{\text{'}}.$ Initially, the pen is

at the origin $(0,0).$

A word over the alphabet $\{u,d,r\}$ represents a sequence of commands and therefore a line. For

example, the word ururdddru represents the line

$($a$)$ A line is a Skyline, if it

does not visit any point twice,

only visits points $(x,y)$ with $y0$ and

ends at a points $(x,0)$ with $x>0.$

In particular, the empty word and the example given above are not Skylines.

Examples for Skylines:

Give a context free grammar which generates all sequences of commands that represent Skylines.

Briefly explain why all words that are generated by your grammar satisfy the three conditions.

$($b$)$ Show that the set of Skyline words is not regular.