Question

Given the following non-deterministic finite state machine: (c) a σ0 o1 σ2 b Find the input set V, the accepting states set T, the states set S, and initial (i) state for the machine. (10/100) Write the transition table for the machine (ii) (10/100) (iii) Write the simplest phrase structure grammar, G=(V,T,S,P), for the machine (10/100) Rewrite the grammar you found in question 4(c)(iii) in BNF notation (iv) (10/100) (v) Is the string aabaaba an accepted string by the finite-state machine? (10/100)

Answer 1

Answers:

i)

Input Set (V) = { a , b }

Accepting States (T) = { σ0 }

States set (S) = { σ0, σ1, σ2 }

Initial State = { σ0 }

ii)

Transition Table

	a	b
*σ0	{σ0,σ1}	Φ
σ1	Φ	σ2
σ2	{σ0,σ2}	σ2

iii)
σ0 -> aσ0|aσ1
σ1 -> bσ2
σ2 -> aσ2|bσ2|aσ0

v) aabaaba is the input string

each value in input string and respective state it goes..
∫(σ0,a) -> σ0
∫(σ0,a) -> σ1
∫(σ1,b) -> σ2
∫(σ2,a) -> σ2
∫(σ2,a) -> σ2
∫(σ2,b) -> σ2
∫(σ2,a) -> σ0

so given input is accepted by the  NFA .