3
$\begingroup$

I have to prove with the pumping lemma that $L$ is not regular or to give a regular expression for that.

Let $L$ be all combinations of commands such that in the complete drawn result no line is drawn above another. At the starting point the pen is down.

The turtle graphic is created by the following commands:

u - pen up
d - pen down
g - go 
l - move 10° left
r - move 10° right

I think think that the language is not regular because I think there is an expression that crosses a line for a big enough $n \in \mathbb N$.

Question: How can I find an expression that helps me to prove that this language is not regular to use the pumping lemma?

And if the language is regular, what technique should I use to find a regular expression?

$\endgroup$
4
  • $\begingroup$ What are the semantics of your language? What does it mean for a line to be crossed? $\endgroup$ Commented Jun 6, 2017 at 10:50
  • $\begingroup$ @YuvalFilmus I have updated my post. Unfotunately I am not given many information in that task. I hope, my post is understandable now. $\endgroup$
    – jublikon
    Commented Jun 6, 2017 at 12:48
  • $\begingroup$ By "crosses a line" do you mean draws a line (with pen down) and later that line is touched by another line (also with pen down), or would you count it as a crossing if the turtle moved over a location it previously occupied? $\endgroup$ Commented Jun 6, 2017 at 15:14
  • $\begingroup$ By "crosses a line" do you mean draws a line (with pen down) and later that line is touched by another line (also with pen down) yes, it means that @RickDecker $\endgroup$
    – jublikon
    Commented Jun 6, 2017 at 15:19

1 Answer 1

2
$\begingroup$

The program $g^nr^9gr^9g^mr^9gr^9g$ crosses a line iff $n \geq m$.

$\endgroup$
2
  • $\begingroup$ Can you please explain why or where do you get $g^nr^9gr^9g^mr^9gr^9g$ from? $\endgroup$
    – jublikon
    Commented Aug 20, 2017 at 9:57
  • $\begingroup$ It would be good to work this out on your own. $\endgroup$ Commented Aug 20, 2017 at 10:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.