You are to write a program to implement the any FSM after learning its structure

Question

You are to write a program to implement the any FSM after learning its structure/definition. Use Java.

Ø  Create a (java) program “yourname-Proj1.java”.

Ø  Step1, In the program, create a function createMachine01() that create example FSM and returns the tuple M = (Q, Sigma, delta, startQ, Final). Where

o   Q: list of states, e.g., [1,2,3,4,…10]

o   Sigma: list of alphabet characters: e.g., [0, 1]

o   delta: two dimensional list (or array) of transitions, e.g., delta[2][1]=0. Delta[fromState][Alphabet input]= toState

§  Therefore, the example delta[2][1]=0 means that the FSM moves from state 2 to state 0 if takes input 1.

§  The array width is len(Sigma) and hight is Len(Q).

§  Filling the whole array means defining all the state transitions.

o   startQ: integer indicating the start state. E.g., startQ= 1

o   Final: set of accepted states e.g., [3,5]

Using the different versions of the above function, you can create different FSMs as follows,

>>> M1= createMachine01() # this function defines example FSM.

>>> M2= createMachine02() # this function defines other example FSM.

Step2, Create a function CheckWord(M, word), that takes an FSM as the variable (list) M generated using createMachine0?() function. It takes also a word (e.g., “01110101”) to check if it belongs to L(M). The function returns True or False.

Step3, create two copies of createMachine0?(): call them createMachine23() and createMachine31() to define the FSM in slides 23 and 31, respectively.

Step4, at the end of the java file, add the following lines

M23= createMachine23()

M31= createMachine31()

CheckWord(M23, “000111”)

CheckWord(M23, “000100”)

CheckWord(M23, “100000”)

CheckWord(M23, “101010”)

CheckWord(M31, “1000111”)

CheckWord(M31, “001100”)

CheckWord(M31, “000011”)

CheckWord(M31, “001001”)

CheckWord(M31, “001101”)

CheckWord(M31, “010000”)

SLIDE 23

SLIDE 31

03- Finite State Automata - Protected View - Saved to this PC AVillera Jamu Home Insert Draw Design Transitions Animations Slide Show Review View Tell me what you want to do PROTECTED VIEW Be carefu-files from the Internet can contain viruses. Unless you need to edit, it's safer to stay in Protected View. En Enable Editing 23 Designing FSM: Example 1 Define an automaton of all binary numbers that does include "100" sequences. 24 25 0,1 0 s0 s1 S2 S3 0 26 27 23 Slide 23 of 106 +80% 9:56 PM O Type here to search 10/17/2017

Explanation / Answer

findmax (40 points)

#

# $a0: the starting address of an asciiz string

# $a1: the starting address of an allocated memory space to which the maximum length word is to

#      be copied, ending with a 0 to make it an asciiz string

#

# Note: Must call the getword function to examine one word at a time

# -----------------------------------------------

# -----------------------------------------------

# getword (40 points)

#

# $a0: the starting address of an asciiz string, say, A, at this address, the content must be the

#      ascii code of an English letter, either upper case of lower case

# $a1: the starting address of an allocated memory space, to which the first word in string A can

#      be copied, ending with a 0 to make it an asciiz string

# $v0: the length of the word

#

# Note: Must call the isletter function

# -----------------------------------------------

# -----------------------------------------------

# isletter (20 points)

#

# $a0: a value

$ $v0: returns 1 if the value in $a0 is the ascii code of an English letter, 0 otherwise

# -----------------------------------------------

"

returnres : .space 100

       .text

       .globl main

main:

       la $a0, dialog

       la $a1, returnres

       jal findmax

       li $v0,4                     # now print the found longest word

       la $a0,returnres

       syscall

      

done:li $v0, 10              # Exit

       syscall

findmax:     

       jr $ra

getword:

       jr $ra

isletter:

       jr $ra

# -----------------------------------------------

# strcpy

#

# Note: copies the string starting at $a1 to an allocated memory space starting at $a0, the same

#       as the code we wrote in the class, will be useful

# -----------------------------------------------

strcpy:      

lb $t0, 0($a1)

       sb $t0, 0($a0)

       addi $a0, $a0, 1

       addi $a1, $a1, 1

       bne $t0, $0, strcpy

       jr $ra

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.