|
Home
| |
The Chomsky Hierarchy
Related Reading: Omnibus Chapters 2, 7,
14, and 23.
Due: Midnight Sunday Feb 17,
2008
- A deterministic finite-state automaton (DFA) is
formally defined as a five-tuple (Q,Σ,δ,q0,qf),
where Q is the set of states, Σ is the alphabet of input
signals, δ is the transition function, and q0 and
qf are the start state and final state, respectively. To
represent this in Haskell, we could define a data type such as:
data DFA = DFA [Int] -- the
set of states is a list of Ints
[Char] -- the alphabet is a list of Chars
Int -- the start state in an Int
[Int] -- the final states are Ints
??? -- the transition function is a ???
Your job is to:
 | Fill in the
??? above. |
| Re-define the
DFA data type so that it
is polymorphic in the type of the states and alphabet. For
example, I may wish to use Chars
for the alphabet and Ints
for states, or Ints
for both, or perhaps Strings
for states and Chars
for the alphabet, and so on. |
| Define a function
runDFA that takes a DFA
and a list of input symbols as input, and returns a
Bool result:
True if the input
sequence is accepted, False
if it isn't.
(The first thing you should do is write a type signature for
runDFA.) |
| To test your code, define a DFA to
recognize the language that consists of:
 | The word "Many", "All", or
"Some", followed by |
| Either one or two of the words
"Funny", "Green", and "Wet" (no duplicates!), followed by |
| The word "Boys", "Girls", or
"Aardvarks", followed by |
| The word "Run", "Sit", or
"Study". |
|
It's now time to write a Haskell
program on your own, from scratch. Your program should implement the
Lindenmayer System described in Chapter 23, which is an example of a
generative context-free grammar. Your program should take a
Lindenmayer grammar as input, and generate an infinite sequence of "sentences"
that are instances of that grammar as output. (Note that this is the
opposite of problem 1 above, which is an example of a recognizer, or
parser, for a grammar.) To do this, some clarifications are
required:
| First, note that the Lindenmayer
grammar shown on Page 158 does not distinguish between terminals and
non-terminals. Thus neither will we, which will in fact simplify our
work. A Lindenmeyer grammer is thus defined to be a
triple (N,s,P), where N is the alphabet,
s is the start symbol, and P is the set of
productions. You should define a data type (as above for DFA's) to
capture this. |
| Also note that every symbol is
rewritten on every step. The output of your program should be the
sequence of sentences that result -- for example, Fig 23.2 shows 7 steps of
this output. However, you don't have to show the result graphically --
for example, the 7th step in Fig 23.2 can be represented as something like:
"b|b|h(a)/g\f/e\d". |
Demonstrate your working program by
duplicating the result shown in Chapter 23 for the red alga.
Solutions.
|
