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)









share|improve this question






















  • 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










  • 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






  • 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















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)









share|improve this question






















  • 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










  • 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






  • 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













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)









share|improve this question













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






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 11 at 0:40









Garibay B Michael

61




61












  • 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










  • 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






  • 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


















  • 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










  • 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






  • 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
















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

















active

oldest

votes











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














 

draft saved


draft discarded


















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






























active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes
















 

draft saved


draft discarded



















































 


draft saved


draft discarded














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





















































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







Popular posts from this blog

Xamarin.iOS Cant Deploy on Iphone

Glorious Revolution

Dulmage-Mendelsohn matrix decomposition in Python