Mihaela Malita

#### Smith College. Fall 2003

## Prolog Programs for Foundations of Computer Science

(More problems will de added..) I expect you to improve the programs and add other programs

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

*Last update: Nov 10, 2003*