DFA in Scheme (homework)
up vote
1
down vote
favorite
Long-time reader, first time poster. Working on a homework question asking to write a DFA-acceptor in Scheme. Alphabet: {0, 1} Start-state: {Q0} Final-state: {Q2}. String must have a 01 in the sequence to be accepted.
States:
Q0 on 1 transitions to Q1.
Q0 on 0 transitions to Q0.
Q1 on 1 transitions to Q2.
Q1 on 0 transitions to P.
Q2 on 0 and 1 transitions to Q1.
The teacher requested each state to be a function and to return a function that it transitions to. (Q0 1) returns Q1, etc. Code below is an attempt to get things running, before worrying about checking if 01 is in the string. Currently getting an error: "Q0: unbound identifier;" and am not sure why after doing some searching. Any pointers would be helpful. The question is for homework, so not looking for direct answers. Thank you!
#lang racket
(define DFA-trans '((Q0 x) (Q1 x) '((Q2 x)) (P x)))
(define x '(1 1 0 1 0))
(define P(null? 1))
(define Q2 (lambda(x)
(if (null? (car x))
#t
(if (equal? (car x) 0)
(Q2 (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#t
)))))
(define Q1 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(P (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#f
)))))
(define Q0 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(Q0 (cdr x))
(if (equal? (car x) 1)
(Q1 (cdr x))
#f
)))))
(define DFA(map eval DFA-trans))
(DFA)
scheme racket dfa
|
show 1 more comment
up vote
1
down vote
favorite
Long-time reader, first time poster. Working on a homework question asking to write a DFA-acceptor in Scheme. Alphabet: {0, 1} Start-state: {Q0} Final-state: {Q2}. String must have a 01 in the sequence to be accepted.
States:
Q0 on 1 transitions to Q1.
Q0 on 0 transitions to Q0.
Q1 on 1 transitions to Q2.
Q1 on 0 transitions to P.
Q2 on 0 and 1 transitions to Q1.
The teacher requested each state to be a function and to return a function that it transitions to. (Q0 1) returns Q1, etc. Code below is an attempt to get things running, before worrying about checking if 01 is in the string. Currently getting an error: "Q0: unbound identifier;" and am not sure why after doing some searching. Any pointers would be helpful. The question is for homework, so not looking for direct answers. Thank you!
#lang racket
(define DFA-trans '((Q0 x) (Q1 x) '((Q2 x)) (P x)))
(define x '(1 1 0 1 0))
(define P(null? 1))
(define Q2 (lambda(x)
(if (null? (car x))
#t
(if (equal? (car x) 0)
(Q2 (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#t
)))))
(define Q1 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(P (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#f
)))))
(define Q0 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(Q0 (cdr x))
(if (equal? (car x) 1)
(Q1 (cdr x))
#f
)))))
(define DFA(map eval DFA-trans))
(DFA)
scheme racket dfa
If it's possible, you should do it without usingeval
.eval
is not necessary for doing this, and right now it'seval
that's causing the "unbound identifier" error.
– Alex Knauth
Nov 11 at 1:02
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
The issue witheval
is with mapping the symbols'Q0
,'Q1
etc. to the function valuesQ0
,Q1
etc, because of namespacing issues. If you can construct theDFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of'(Q0 (1 1 0))
, try writing(list Q0 (list 1 1 0))
.
– Alex Knauth
Nov 11 at 1:18
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
1
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying thateval
isn't working for you, that you're getting "unbound identifier" from even simple programs like#lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without usingeval
at all.
– Alex Knauth
Nov 11 at 1:32
|
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Long-time reader, first time poster. Working on a homework question asking to write a DFA-acceptor in Scheme. Alphabet: {0, 1} Start-state: {Q0} Final-state: {Q2}. String must have a 01 in the sequence to be accepted.
States:
Q0 on 1 transitions to Q1.
Q0 on 0 transitions to Q0.
Q1 on 1 transitions to Q2.
Q1 on 0 transitions to P.
Q2 on 0 and 1 transitions to Q1.
The teacher requested each state to be a function and to return a function that it transitions to. (Q0 1) returns Q1, etc. Code below is an attempt to get things running, before worrying about checking if 01 is in the string. Currently getting an error: "Q0: unbound identifier;" and am not sure why after doing some searching. Any pointers would be helpful. The question is for homework, so not looking for direct answers. Thank you!
#lang racket
(define DFA-trans '((Q0 x) (Q1 x) '((Q2 x)) (P x)))
(define x '(1 1 0 1 0))
(define P(null? 1))
(define Q2 (lambda(x)
(if (null? (car x))
#t
(if (equal? (car x) 0)
(Q2 (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#t
)))))
(define Q1 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(P (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#f
)))))
(define Q0 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(Q0 (cdr x))
(if (equal? (car x) 1)
(Q1 (cdr x))
#f
)))))
(define DFA(map eval DFA-trans))
(DFA)
scheme racket dfa
Long-time reader, first time poster. Working on a homework question asking to write a DFA-acceptor in Scheme. Alphabet: {0, 1} Start-state: {Q0} Final-state: {Q2}. String must have a 01 in the sequence to be accepted.
States:
Q0 on 1 transitions to Q1.
Q0 on 0 transitions to Q0.
Q1 on 1 transitions to Q2.
Q1 on 0 transitions to P.
Q2 on 0 and 1 transitions to Q1.
The teacher requested each state to be a function and to return a function that it transitions to. (Q0 1) returns Q1, etc. Code below is an attempt to get things running, before worrying about checking if 01 is in the string. Currently getting an error: "Q0: unbound identifier;" and am not sure why after doing some searching. Any pointers would be helpful. The question is for homework, so not looking for direct answers. Thank you!
#lang racket
(define DFA-trans '((Q0 x) (Q1 x) '((Q2 x)) (P x)))
(define x '(1 1 0 1 0))
(define P(null? 1))
(define Q2 (lambda(x)
(if (null? (car x))
#t
(if (equal? (car x) 0)
(Q2 (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#t
)))))
(define Q1 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(P (cdr x))
(if (equal? (car x) 1)
(Q2 (cdr x))
#f
)))))
(define Q0 (lambda(x)
(if (null? (car x))
#f
(if (equal? (car x) 0)
(Q0 (cdr x))
(if (equal? (car x) 1)
(Q1 (cdr x))
#f
)))))
(define DFA(map eval DFA-trans))
(DFA)
scheme racket dfa
scheme racket dfa
asked Nov 11 at 0:40
Garibay B Michael
61
61
If it's possible, you should do it without usingeval
.eval
is not necessary for doing this, and right now it'seval
that's causing the "unbound identifier" error.
– Alex Knauth
Nov 11 at 1:02
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
The issue witheval
is with mapping the symbols'Q0
,'Q1
etc. to the function valuesQ0
,Q1
etc, because of namespacing issues. If you can construct theDFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of'(Q0 (1 1 0))
, try writing(list Q0 (list 1 1 0))
.
– Alex Knauth
Nov 11 at 1:18
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
1
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying thateval
isn't working for you, that you're getting "unbound identifier" from even simple programs like#lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without usingeval
at all.
– Alex Knauth
Nov 11 at 1:32
|
show 1 more comment
If it's possible, you should do it without usingeval
.eval
is not necessary for doing this, and right now it'seval
that's causing the "unbound identifier" error.
– Alex Knauth
Nov 11 at 1:02
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
The issue witheval
is with mapping the symbols'Q0
,'Q1
etc. to the function valuesQ0
,Q1
etc, because of namespacing issues. If you can construct theDFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of'(Q0 (1 1 0))
, try writing(list Q0 (list 1 1 0))
.
– Alex Knauth
Nov 11 at 1:18
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
1
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying thateval
isn't working for you, that you're getting "unbound identifier" from even simple programs like#lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without usingeval
at all.
– Alex Knauth
Nov 11 at 1:32
If it's possible, you should do it without using
eval
. eval
is not necessary for doing this, and right now it's eval
that's causing the "unbound identifier" error.– Alex Knauth
Nov 11 at 1:02
If it's possible, you should do it without using
eval
. eval
is not necessary for doing this, and right now it's eval
that's causing the "unbound identifier" error.– Alex Knauth
Nov 11 at 1:02
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
The issue with
eval
is with mapping the symbols 'Q0
, 'Q1
etc. to the function values Q0
, Q1
etc, because of namespacing issues. If you can construct the DFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of '(Q0 (1 1 0))
, try writing (list Q0 (list 1 1 0))
.– Alex Knauth
Nov 11 at 1:18
The issue with
eval
is with mapping the symbols 'Q0
, 'Q1
etc. to the function values Q0
, Q1
etc, because of namespacing issues. If you can construct the DFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of '(Q0 (1 1 0))
, try writing (list Q0 (list 1 1 0))
.– Alex Knauth
Nov 11 at 1:18
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
1
1
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying that
eval
isn't working for you, that you're getting "unbound identifier" from even simple programs like #lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without using eval
at all.– Alex Knauth
Nov 11 at 1:32
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying that
eval
isn't working for you, that you're getting "unbound identifier" from even simple programs like #lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without using eval
at all.– Alex Knauth
Nov 11 at 1:32
|
show 1 more comment
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53244813%2fdfa-in-scheme-homework%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
If it's possible, you should do it without using
eval
.eval
is not necessary for doing this, and right now it'seval
that's causing the "unbound identifier" error.– Alex Knauth
Nov 11 at 1:02
I was utilizing map eval per the teachers suggestion to tackle the problem. He wants the call to start things off to be: (DFA-Acceptor <list of alphabets in string to be accepted> <start-state> (<list of final states>) <sink-state>). Due to the final state being a list of states (even though it's just Q2), he suggested map eval.
– Garibay B Michael
Nov 11 at 1:13
The issue with
eval
is with mapping the symbols'Q0
,'Q1
etc. to the function valuesQ0
,Q1
etc, because of namespacing issues. If you can construct theDFA-trans
list without using quote ('
), then eval won't give you as much of a problem. For example, instead of'(Q0 (1 1 0))
, try writing(list Q0 (list 1 1 0))
.– Alex Knauth
Nov 11 at 1:18
Ahh, I see. Thank you for your input. I'll play with that for a bit, but am leaning towards your original suggestion of dropping eval. I think I see a solution utilizing most of my current code.
– Garibay B Michael
Nov 11 at 1:27
1
Does your teacher have a place, either an Office or an online forum, where you can ask questions about these things? Try saying that
eval
isn't working for you, that you're getting "unbound identifier" from even simple programs like#lang racket (define x 5) (eval 'x)
, and ask if there's a way to do this without usingeval
at all.– Alex Knauth
Nov 11 at 1:32