185A-Assignment 4 Solved

points
Please convert the following graphical representation of an FSA into our Haskell format with the type Automaton:

(1)

 

Specifically, define fsa_1 to be the appropriate thing of type Automaton to represent this FSA. You can use the functions recognize and hat to test the behavior of your implementation:

(2)       Example behavior:

 recognize fsa_1 [True, False, True, True, False] Ô⇒∗ True recognize fsa_1 [True, True, True, False, True, True] Ô⇒∗ False hat (transitions fsa_1) 54 [True, False, True, True] Ô⇒∗ [38, 54] hat (transitions fsa_1) 73 [True, False, True, True] Ô⇒∗ [73]

                                                                                                                               25 points
Please construct the following FSAs in Haskell with the type Automaton. You may choose to use whatever you want as the state type (though Int is a natural choice in most cases). You can use recognize to test the behavior of your implementation.

(3)             a.          Construct an FSA called fsa_2 that has SegmentCV as its alphabet, and generates all and only those sequences that contain at least two Cs.

Example behavior:

recognize fsa_2 [C,C,C,C]
recognize fsa_2 [V,V,C,V]
Ô⇒∗ True Ô⇒∗ False

b.       Construct an FSA called fsa_3 that has SegmentCV as its alphabet, and generates all and only those sequences that have an odd number of Cs and an even number of Vs (treating zero as an even number).

Example behavior:

recognize fsa_3 [C]
∗

Ô⇒ True
recognize fsa_3 [C, V, V]
∗

Ô⇒

∗

Ô⇒
recognize fsa_3 [C, C, V]
recognize fsa_3 [C, C, V, C, V]
 
 
 
True

False

Ô⇒∗ False

c.        Construct an FSA called fsa_4 that has SegmentCV as its alphabet, and generates all and only those sequences that have C as their third-to-last symbol.

Example behavior:

recognize fsa_4 [C, C, C, V, C]
recognize fsa_4 [C, C, V, V, C]
Ô⇒∗ True Ô⇒∗ False

d.       Construct an FSA called fsa_5 that has SegmentPKIU as its alphabet, which enforces a simple kind of vowel harmony: treating WB as the wordboundary symbol, all the vowels within a word must be identical to each other. Any sequences built out of the symbols P, K, I, U, and WB are allowed

as long as they satisfy this requirement. This includes some strange ones such as those that contain two adjacent “word boundaries”, and those including “words” that contain no vowels, etc.; the goal here is just to isolate the vowel-harmony requirement itself.

Example behavior:

recognize fsa_5 [P, K, I, K, WB, U, P, U]
recognize fsa_5 [P, K, I, K, U, P, U]
Ô⇒

False
recognize fsa_5 [K, P, P, P]
∗

Ô⇒ True

∗

Ô⇒
recognize fsa_5 [K, I, P, U]
Ô⇒∗ True

∗ False

e.       Construct an FSA called fsa_6 that has SegmentPKIU as its alphabet, and generates all and only those sequences that (i) do not contain WB, and (ii) satisfy the requirement that U can only appear somewhere after a P.

Example behavior:

recognize fsa_6 [P, U]
∗

Ô⇒ True

∗

Ô⇒ False
recognize fsa_6 [U, P]
recognize fsa_6 [P, K, K, K, K, K, K, U]
recognize fsa_6 [K, K, K, K, K, K, K, K]
Ô⇒∗ True

Ô⇒∗ True