knuth ~:228> pl -f pflapTest.pl % pflap compiled 0.00 sec, 52,600 bytes % /home/keller/pflapTest.pl compiled 0.00 sec, 94,856 bytes Welcome to SWI-Prolog (Multi-threaded, Version 5.6.17) Copyright (c) 1990-2006 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- test. DFA: States = [q0, q1, q2] Alphabet = [a, b] Initial = q0 Final = [q2] Transitions: q0, a, q0 q0, b, q1 q1, a, q0 q1, b, q2 q2, a, q0 q2, b, q1 Input string: aabb accepted by state sequence [q0, q0, q0, q1, q2]. Input string: abba not accepted by state sequence [q0, q0, q1, q2, q0]. DFA: States = [q0, q1, q2] Alphabet = [a, b] Initial = q0 Final = [q2] Transitions: q0, a, q0 q0, b, q1 q1, a, q0 q1, b, q2 q2, a, q0 q2, b, q1 Sequences accepted to length 5: bb abb aabb babb bbbb aaabb ababb abbbb baabb bbabb DFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial = q0 Final = [q0] Transitions: q0, 0, q0 q0, 1, q1 q1, 0, q2 q1, 1, q0 q2, 0, q1 q2, 1, q2 Sequences accepted to length 5: 0 00 11 000 011 110 0000 0011 0110 1001 1100 1111 00000 00011 00110 01001 01100 01111 10010 10101 11000 11011 11110 NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0] Final = [q0, q1] Transitions: q0, 0, q0 q0, 0, q1 q0, 1, q1 q1, 0, q2 q1, 1, q0 q1, 1, q1 q2, 0, q1 q2, 1, q2 Input string 10 not accepted (no accepting sequence). Input string 010 accepted by state sequence [q0, q1, q0, q0]. NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0] Final = [q0, q1] Transitions: q0, 0, q0 q0, 0, q1 q0, 1, q1 q1, 0, q2 q1, 1, q0 q1, 1, q1 q2, 0, q1 q2, 1, q2 Sequences accepted in up to 5 steps: 0 1 00 01 11 000 001 010 011 100 110 111 0000 0001 0010 0011 0100 0101 0110 0111 1001 1010 1100 1101 1110 1111 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10010 10011 10101 10110 11000 11001 11010 11011 11100 11101 11110 11111 NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0] Final = [q2] Transitions: q0, 0, q0 q0, [], q1 q1, 0, q0 q1, 1, q2 Input string 01 accepted by state sequence [q0, q0, q1, q2]. Input string 00 not accepted (no accepting sequence). NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0] Final = [q2] Transitions: q0, 0, q0 q0, [], q1 q1, 0, q0 q1, 1, q2 Sequences accepted in up to 10 steps: 1 01 001 0001 00001 000001 0000001 00000001 000000001 NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0, q1] Final = [q2] Transitions: q0, 0, q2 q1, 1, q2 q1, 1, q1 Input string 01 not accepted (no accepting sequence). Input string 11 accepted by state sequence [q1, q1, q2]. NFA: States = [q0, q1, q2] Alphabet = [0, 1] Initial State Set= [q0, q1] Final = [q2] Transitions: q0, 0, q2 q1, 1, q2 q1, 1, q1 Sequences accepted in up to 10 steps: 0 1 11 111 1111 11111 111111 1111111 11111111 111111111 1111111111 NFA: States = [q0, q1] Alphabet = [0, 1] Initial State Set= [q0] Final = [q0] Transitions: q0, 0, q1 q0, 1, q1 Sequences accepted in up to 10 steps: NFA: States = [s, z, a, b, c] Alphabet = [a, b] Initial State Set= [s] Final = [c, z] Transitions: s, a, z s, [], a a, a, a a, b, b b, a, c b, b, a b, b, b c, a, a Sequences accepted in up to 10 steps: a ba aba bba aaba abba bbba aaaba aabba abbba baaba bbaba bbbba aaaaba aaabba aabbba abaaba abbaba abbbba baaaba baabba bbaaba bbabba bbbaba bbbbba aaaaaba aaaabba aaabbba aabaaba aabbaba aabbbba abaaaba abaabba abbaaba abbabba abbbaba abbbbba baaaaba baaabba baabbba bbaaaba bbaabba bbabbba bbbaaba bbbabba bbbbaba bbbbbba aaaaaaba aaaaabba aaaabbba aaabaaba aaabbaba aaabbbba aabaaaba aabaabba aabbaaba aabbabba aabbbaba aabbbbba abaaaaba abaaabba abaabbba abbaaaba abbaabba abbabbba abbbaaba abbbabba abbbbaba abbbbbba baaaaaba baaaabba baaabbba baabaaba baabbaba baabbbba bbaaaaba bbaaabba bbaabbba bbabaaba bbabbaba bbabbbba bbbaaaba bbbaabba bbbabbba bbbbaaba bbbbabba bbbbbaba bbbbbbba aaaaaaaba aaaaaabba aaaaabbba aaaabaaba aaaabbaba aaaabbbba aaabaaaba aaabaabba aaabbaaba aaabbabba aaabbbaba aaabbbbba aabaaaaba aabaaabba aabaabbba aabbaaaba aabbaabba aabbabbba aabbbaaba aabbbabba aabbbbaba aabbbbbba abaaaaaba abaaaabba abaaabbba abaabaaba abaabbaba abaabbbba abbaaaaba abbaaabba abbaabbba abbabaaba abbabbaba abbabbbba abbbaaaba abbbaabba abbbabbba abbbbaaba abbbbabba abbbbbaba abbbbbbba baaaaaaba baaaaabba baaaabbba baaabaaba baaabbaba baaabbbba baabaaaba baabaabba baabbaaba baabbabba baabbbaba baabbbbba bbaaaaaba bbaaaabba bbaaabbba bbaabaaba bbaabbaba bbaabbbba bbabaaaba bbabaabba bbabbaaba bbabbabba bbabbbaba bbabbbbba bbbaaaaba bbbaaabba bbbaabbba bbbabaaba bbbabbaba bbbabbbba bbbbaaaba bbbbaabba bbbbabbba bbbbbaaba bbbbbabba bbbbbbaba bbbbbbbba PDA: States = [q0] StackAlphabet = [s, r, a, b, [, ], (,)] Initial Stack = s Alphabet = [a, b, [, ], (,)] Initial State = q0 Accept States = [] Transitions: s, q0, [], [[, ]], q0 s, q0, [], [[, s, r], q0 s, q0, [], [a], q0 s, q0, [], [b], q0 r, q0, [], []], q0 r, q0, [], [ (,), s, r], q0 a, q0, a, [], q0 b, q0, b, [], q0 [, q0, [, [], q0 ], q0, ], [], q0 (,), q0, (,), [], q0 Input string a accepted by state sequence [ ([s], q0), ([a], q0), ([], q0)]. Input string ] not accepted. Input string [ not accepted. Input string [a] accepted by state sequence [ ([s], q0), ([[, s, r], q0), ([s, r], q0), ([a, r], q0), ([r], q0), ([]], q0), ([], q0)]. Input string [a,b] accepted by state sequence [ ([s], q0), ([[, s, r], q0), ([s, r], q0), ([a, r], q0), ([r], q0), ([ (,), s, r], q0), ([s, r], q0), ([b, r], q0), ([r], q0), ([]], q0), ([], q0)]. Input string [a,[b]] accepted by state sequence [ ([s], q0), ([[, s, r], q0), ([s, r], q0), ([a, r], q0), ([r], q0), ([ (,), s, r], q0), ([s, r], q0), ([[, s, r, r], q0), ([s, r, r], q0), ([b, r, r], q0), ([r, r], q0), ([], r], q0), ([r], q0), ([]], q0), ([], q0)]. Input string [a,[b] not accepted. Input string [a,[b,a]] accepted by state sequence [ ([s], q0), ([[, s, r], q0), ([s, r], q0), ([a, r], q0), ([r], q0), ([ (,), s, r], q0), ([s, r], q0), ([[, s, r, r], q0), ([s, r, r], q0), ([b, r, r], q0), ([r, r], q0), ([ (,), s, r, r], q0), ([s, r, r], q0), ([a, r, r], q0), ([r, r], q0), ([], r], q0), ([r], q0), ([]], q0), ([], q0)]. PDA: States = [q0] StackAlphabet = [s, r, a, b, [, ], (,)] Initial Stack = s Alphabet = [a, b, [, ], (,)] Initial State = q0 Accept States = [] Transitions: s, q0, [], [[, ]], q0 s, q0, [], [[, s, r], q0 s, q0, [], [a], q0 s, q0, [], [b], q0 r, q0, [], []], q0 r, q0, [], [ (,), s, r], q0 a, q0, a, [], q0 b, q0, b, [], q0 [, q0, [, [], q0 ], q0, ], [], q0 (,), q0, (,), [], q0 Sequences accepted in up to 15 steps: a b [] [a] [b] [[]] [[a]] [[b]] [a,a] [a,b] [b,a] [b,b] [[[]]] [[],a] [[],b] [a,[]] [b,[]] [[[a]]] [[[b]]] [[],[]] [[a,a]] [[a,b]] [[a],a] [[a],b] [[b,a]] [[b,b]] [[b],a] [[b],b] [a,[a]] [a,[b]] [a,a,a] [a,a,b] [a,b,a] [a,b,b] [b,[a]] [b,[b]] [b,a,a] [b,a,b] [b,b,a] [b,b,b] [[[[]]]] [[[],a]] [[[],b]] [[[]],a] [[[]],b] [[],[a]] [[],[b]] [[],a,a] [[],a,b] [[],b,a] [[],b,b] [[a,[]]] [[a],[]] [[b,[]]] [[b],[]] [a,[[]]] [a,[],a] [a,[],b] [a,a,[]] [a,b,[]] [b,[[]]] [b,[],a] [b,[],b] [b,a,[]] [b,b,[]] DFA: States = [q0, q1, q2] Alphabet = [a, b] Initial = q0 Final = [q1] Transitions: q0, a, q0 q0, b, q1 q1, a, q0 q1, b, q1 q2, a, q0 q2, b, q1 DFA: States = [[q1], [q0, q2]] Alphabet = [a, b] Initial = [q0, q2] Final = [[q1]] Transitions: [q1], a, [q0, q2] [q1], b, [q1] [q0, q2], a, [q0, q2] [q0, q2], b, [q1] PDA: States = [q0] StackAlphabet = [s, a, b] Initial Stack = s Alphabet = [a, b] Initial State = q0 Accept States = [] Transitions: s, q0, a, [a, s], q0 s, q0, b, [b, s], q0 a, q0, a, [a, a], q0 a, q0, b, [b, a], q0 b, q0, a, [a, b], q0 b, q0, b, [b, b], q0 a, q0, [], [a], q1 b, q0, [], [b], q1 a, q1, a, [], q1 b, q1, b, [], q1 s, q1, [], [], q1 Input string abba accepted by state sequence [ ([s], q0), ([a, s], q0), ([b, a, s], q0), ([b, a, s], q1), ([a, s], q1), ([s], q1), ([], q1)]. Input string abbb not accepted. PDA: States = [q0] StackAlphabet = [s, a, b] Initial Stack = s Alphabet = [a, b] Initial State = q0 Accept States = [] Transitions: s, q0, a, [a, s], q0 s, q0, b, [b, s], q0 a, q0, a, [a, a], q0 a, q0, b, [b, a], q0 b, q0, a, [a, b], q0 b, q0, b, [b, b], q0 a, q0, [], [a], q1 b, q0, [], [b], q1 a, q1, a, [], q1 b, q1, b, [], q1 s, q1, [], [], q1 Sequences accepted in up to 9 steps: aa bb aaaa abba baab bbbb aaaaaa aabbaa abaaba abbbba baaaab babbab bbaabb bbbbbb PDA: States = [q0] StackAlphabet = [s, a, b] Initial Stack = x Alphabet = [a, b] Initial State = u Accept States = [] Transitions: x, u, [], [ (q0, s, q0)], u x, u, [], [ (q0, s, q1)], u (q0, s, q0), u, a, [ (q0, a, q0), (q0, s, q0)], u (q0, s, q1), u, a, [ (q0, a, q0), (q0, s, q1)], u (q0, s, q0), u, a, [ (q0, a, q1), (q1, s, q0)], u (q0, s, q1), u, a, [ (q0, a, q1), (q1, s, q1)], u (q0, s, q0), u, b, [ (q0, b, q0), (q0, s, q0)], u (q0, s, q1), u, b, [ (q0, b, q0), (q0, s, q1)], u (q0, s, q0), u, b, [ (q0, b, q1), (q1, s, q0)], u (q0, s, q1), u, b, [ (q0, b, q1), (q1, s, q1)], u (q0, a, q0), u, a, [ (q0, a, q0), (q0, a, q0)], u (q0, a, q1), u, a, [ (q0, a, q0), (q0, a, q1)], u (q0, a, q0), u, a, [ (q0, a, q1), (q1, a, q0)], u (q0, a, q1), u, a, [ (q0, a, q1), (q1, a, q1)], u (q0, a, q0), u, b, [ (q0, b, q0), (q0, a, q0)], u (q0, a, q1), u, b, [ (q0, b, q0), (q0, a, q1)], u (q0, a, q0), u, b, [ (q0, b, q1), (q1, a, q0)], u (q0, a, q1), u, b, [ (q0, b, q1), (q1, a, q1)], u (q0, b, q0), u, a, [ (q0, a, q0), (q0, b, q0)], u (q0, b, q1), u, a, [ (q0, a, q0), (q0, b, q1)], u (q0, b, q0), u, a, [ (q0, a, q1), (q1, b, q0)], u (q0, b, q1), u, a, [ (q0, a, q1), (q1, b, q1)], u (q0, b, q0), u, b, [ (q0, b, q0), (q0, b, q0)], u (q0, b, q1), u, b, [ (q0, b, q0), (q0, b, q1)], u (q0, b, q0), u, b, [ (q0, b, q1), (q1, b, q0)], u (q0, b, q1), u, b, [ (q0, b, q1), (q1, b, q1)], u (q0, a, q0), u, [], [ (q1, a, q0)], u (q0, a, q1), u, [], [ (q1, a, q1)], u (q0, b, q0), u, [], [ (q1, b, q0)], u (q0, b, q1), u, [], [ (q1, b, q1)], u (q1, a, q1), u, a, [], u (q1, b, q1), u, b, [], u (q1, s, q1), u, [], [], u Input string abba accepted by state sequence [ ([x], u), ([ (q0, s, q1)], u), ([ (q0, a, q1), (q1, s, q1)], u), ([ (q0, b, q1), (q1, a, q1), (q1, s, q1)], u), ([ (q1, b, q1), (q1, a, q1), (q1, s, q1)], u), ([ (q1, a, q1), (q1, s, q1)], u), ([ (q1, s, q1)], u), ([], u)]. Input string abbb not accepted. PDA: States = [q0] StackAlphabet = [s, a, b] Initial Stack = x Alphabet = [a, b] Initial State = u Accept States = [] Transitions: x, u, [], [ (q0, s, q0)], u x, u, [], [ (q0, s, q1)], u (q0, s, q0), u, a, [ (q0, a, q0), (q0, s, q0)], u (q0, s, q1), u, a, [ (q0, a, q0), (q0, s, q1)], u (q0, s, q0), u, a, [ (q0, a, q1), (q1, s, q0)], u (q0, s, q1), u, a, [ (q0, a, q1), (q1, s, q1)], u (q0, s, q0), u, b, [ (q0, b, q0), (q0, s, q0)], u (q0, s, q1), u, b, [ (q0, b, q0), (q0, s, q1)], u (q0, s, q0), u, b, [ (q0, b, q1), (q1, s, q0)], u (q0, s, q1), u, b, [ (q0, b, q1), (q1, s, q1)], u (q0, a, q0), u, a, [ (q0, a, q0), (q0, a, q0)], u (q0, a, q1), u, a, [ (q0, a, q0), (q0, a, q1)], u (q0, a, q0), u, a, [ (q0, a, q1), (q1, a, q0)], u (q0, a, q1), u, a, [ (q0, a, q1), (q1, a, q1)], u (q0, a, q0), u, b, [ (q0, b, q0), (q0, a, q0)], u (q0, a, q1), u, b, [ (q0, b, q0), (q0, a, q1)], u (q0, a, q0), u, b, [ (q0, b, q1), (q1, a, q0)], u (q0, a, q1), u, b, [ (q0, b, q1), (q1, a, q1)], u (q0, b, q0), u, a, [ (q0, a, q0), (q0, b, q0)], u (q0, b, q1), u, a, [ (q0, a, q0), (q0, b, q1)], u (q0, b, q0), u, a, [ (q0, a, q1), (q1, b, q0)], u (q0, b, q1), u, a, [ (q0, a, q1), (q1, b, q1)], u (q0, b, q0), u, b, [ (q0, b, q0), (q0, b, q0)], u (q0, b, q1), u, b, [ (q0, b, q0), (q0, b, q1)], u (q0, b, q0), u, b, [ (q0, b, q1), (q1, b, q0)], u (q0, b, q1), u, b, [ (q0, b, q1), (q1, b, q1)], u (q0, a, q0), u, [], [ (q1, a, q0)], u (q0, a, q1), u, [], [ (q1, a, q1)], u (q0, b, q0), u, [], [ (q1, b, q0)], u (q0, b, q1), u, [], [ (q1, b, q1)], u (q1, a, q1), u, a, [], u (q1, b, q1), u, b, [], u (q1, s, q1), u, [], [], u Sequences accepted in up to 10 steps: aa bb aaaa abba baab bbbb aaaaaa aabbaa abaaba abbbba baaaab babbab bbaabb bbbbbb PDA: States = [a, b] StackAlphabet = [s, 0] Initial Stack = s Alphabet = [0, 1] Initial State = a Accept States = [] Transitions: s, a, [], [], a s, a, 0, [0, s], a 0, a, 0, [0, 0], a 0, a, 1, [], b 0, b, 1, [], b s, b, [], [], b Sequences accepted in up to 10 steps: 01 0011 000111 00001111 PDA: States = [u] StackAlphabet = [x, (a, s, a), (a, 0, a), (a, 0, b), (b, 0, b), (b, s, b)] Initial Stack = x Alphabet = [0, 1] Initial State = u Accept States = [] Transitions: x, u, [], [ (a, s, a)], u x, u, [], [ (a, s, b)], u (a, s, a), u, [], [], u (a, s, a), u, 0, [ (a, 0, a), (a, s, a)], u (a, s, a), u, 0, [ (a, 0, b), (b, s, a)], u (a, s, b), u, 0, [ (a, 0, a), (a, s, b)], u (a, s, b), u, 0, [ (a, 0, b), (b, s, b)], u (a, 0, a), u, 0, [ (a, 0, a), (a, 0, a)], u (a, 0, a), u, 0, [ (a, 0, b), (b, 0, a)], u (a, 0, b), u, 0, [ (a, 0, a), (a, 0, b)], u (a, 0, b), u, 0, [ (a, 0, b), (b, 0, b)], u (a, 0, b), u, 1, [], u (b, 0, b), u, 1, [], u (b, s, b), u, [], [], u Sequences accepted in up to 10 steps: 01 0011 000111 00001111 Yes ?-