Smith College. Fall 2003

Prolog Programs for Foundations of Computer Science

1. dfa0 Describe a DFA
2. dfa1 Check if DFA is well defined
3. dfa2 Check if DFA or NFA. Part I. If the transtion function is defined for all States X Letters
4. dfa3 Print the DFA
5. dfa4 Check if a word is accepted by the DFA
6. dfa5 If a word is accepted by DFA. Print path
7. dfa6 Check if a DFA accepts any words of certain length
8. dfa7 Empty word problem. Check if a DFA accepts any words
9. nfa0 Check if a word is accepted by a NFA. Print path
10. fa0 Report if a FA is a DFA or NFA. (improve Part I)
11. gram1 Grammar for L(G)= a^n b^n Words as lists
12. gram2 Grammar for L(G)= a^n b^n Improved
13. gram3 Grammar for L(G)= a^n b^n Look in a file exgram0.txt
14. chom0 First grammar to build sentences in English
15. chom1 A grammar to build sentences in English. Plural/Singular
16. parse0 Parsing a sentence
17. stack0 A STACK in Prolog
18. pda0 A PushDown Automaton for a^nb^n
19. pda1 A PushDown Automaton for EQUAL
20. pda2 A PushDown Automaton for Even Palidromes (another way to implement the Stack)
21. pda3 Check if a PDA (pushdown automaton) is NPDA (nondeterministic) or DPDA (deterministic)
22. npda4 NPDA for L={w b v| w,v in {a,b}*; |w| = |v|} by Oluwatoyin Abogan (Solution to Hwk9b)
23. npda5 NPDA for L={a^m b^2m | m = 0,1,2,...} by Amanda Ricketson (Solution to Hwk9-1 Problem 3.22)
24. npda6 NPDA for L={a^nbw | |bw| = n w is {a,b}*} by Intisar Bashir (Solution to Hwk9 Problem 3.20)
25. pda7 A Pushdown Automaton for a^m b^k c^m by Cristina Harko (Solution to Hwk10 (Ex 3.42 a), page 117)
26. gen0 Generate words over an alphabet
27. empty0 The emptiness problem. L(G)= 0 ?
28. empty1 The emptiness problem. L(G)= 0 ? Generate words.
29. empty2 The emptiness problem. L(G)= 0 ? Generate till first word found.
30. turing0 A Turing Machine that erases the input string
31. turing1 A Turing Machine that adds two unary numbers
32. turing2 A Turing Machine for recognizing a^nb^n
33. turing3 A Turing Machine for checking if an unary number is even or odd
34. turing4 A Turing Machine for recognizing a^n b^n c^n
35. turing5 A Turing Machine for INCREMENTing a binary number
36. turing6 A Turing Machine for DECREMENTing a binary number
37. turing7 A Turing Machine for testing ZEROs
38. turing9 A Turing Machine for COPY (DUPLICATE) only a's
39. turing10 A Turing Machine for COPY (DUPLICATE) w from {a,b}*
40. turing11 A Turing Machine for COPY (DUPLICATE) w from {a,b}* with Register*
41. turing12 A Turing Machine for SORTING
42. turing13 Check if Turing Machine is deterministic