When aiming to create a deterministic PDA for the given language, L = {a^(m)b^(n)c^(p) | n does not equal p}, I had come up with the following pda, along with tests that should in theory work:
#lang fsm
(define bncp-pda
(make-ndpda '(S A B C D F)
'(a b c z)
'(y b)
'S
'(F)
`(((S a ,EMP) (S ,EMP)) ; Ignore 'a's at the start
((S b ,EMP) (A (y))) ; Start processing 'b's, push 'y' as bottom marker
((A b ,EMP) (B (b))) ; Continue processing 'b's, push 'b'
((B b ,EMP) (B (b))) ; Continue processing 'b's, push 'b'
((B c (b)) (C ,EMP)) ; Start processing 'c's, pop 'b'
((C c (b)) (C ,EMP)) ; Continue processing 'c's, pop 'b'
((C z ,EMP) (D ,EMP)) ; Check for stack balance at end, move to D if unbalanced
((B z ,EMP) (D ,EMP)) ; More 'b's than 'c's, check in D
((D ,EMP ,EMP) (F ,EMP)) ; Final state check, accept if stack balanced
((C c ,EMP) (D ,EMP))))) ; More 'c's than 'b's, handle in D
(check-equal? (sm-apply bncp-pda '(a a b b c z)) 'accept) ; Accepted, more 'b's than 'c's
(check-equal? (sm-apply bncp-pda '(b c c z)) 'accept) ; Accepted, more 'c's than 'b's
(check-equal? (sm-apply bncp-pda '(a a c c c z)) 'accept) ; Accepted, no 'b's, only 'c's
(check-equal? (sm-apply bncp-pda '(a b b b z)) 'accept) ; Accepted, no 'c's, only 'b's
(check-equal? (sm-apply bncp-pda '(b b c c z)) 'reject) ; Rejected, equal 'b's and 'c's
(check-equal? (sm-apply bncp-pda '(a a a z)) 'reject) ; Rejected, no 'b's or 'c's
(check-equal? (sm-apply bncp-pda '(a b b c c)) 'reject) ; Rejected, no end marker 'z'
(check-equal? (sm-apply bncp-pda '(a c c b b z)) 'reject) ; Rejected, 'c's before 'b's
Yet when running program, all the tests that should be accepting are failing, and I don’t necessarily know which aspect is of the pda is causing the issues. I had based my program on an example deterministic pda, in which this ones given language was: L = {a^(m)b^(n)c^(p) | m ≠ n ∧ m,n,p>0}.
- Example deterministic pda:
#lang fsm
(define ambncp (make-ndpda '(S A B C D E F G)
'(a b c z)
'(a y)
'S
'(F)
`(((S a ,EMP) (A (a y)))
((A a ,EMP) (A (a)))
((A b (a)) (B ,EMP))
((B b (a)) (B ,EMP))
((B c (a)) (C ,EMP))
((C c (a)) (C ,EMP))
((C z ,EMP) (G ,EMP))
((C c (y)) (E (y)))
((B b (y)) (D (y)))
((D b (y)) (D (y)))
((D c (y)) (E (y)))
((E c (y)) (E (y)))
((E z (y)) (F ,EMP))
((G ,EMP (a)) (G ,EMP))
((G ,EMP (y)) (F ,EMP)))))
(check-equal? (sm-apply ambncp '(z)) 'reject)
(check-equal? (sm-apply ambncp '(a b b c c)) 'reject)
(check-equal? (sm-apply ambncp '(a a b b c c z)) 'reject)
(check-equal? (sm-apply ambncp '(a b a z)) 'reject)
(check-equal? (sm-apply ambncp '(a b b z)) 'reject)
(check-equal? (sm-apply ambncp '(a a a b b c c z)) 'accept)
(check-equal? (sm-apply ambncp '(a a a b c z)) 'accept)
(check-equal? (sm-apply ambncp '(a a a b b b b c c c z)) 'accept)
The main aspect that I had tried was by modifying aspects of the States, and the transitions, to see if they would have any effect toward the program properly accepting or rejecting strings that are not compatible with the language. Yet any changes that I had made, the following errors would occur for the tests that I expected to accepted:
. FAILURE
name: check-equal?
location: 19-unsaved-editor:20:0
actual: ‘reject
expected: ‘accept
. FAILURE
name: check-equal?
location: 19-unsaved-editor:21:0
actual: ‘reject
expected: ‘accept
. FAILURE
name: check-equal?
location: 19-unsaved-editor:22:0
actual: ‘reject
expected: ‘accept
. FAILURE
name: check-equal?
location: 19-unsaved-editor:23:0
actual: ‘reject
expected: ‘accept
Raw_Pickle is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.