CS403/SE307/CS355 - Theory of Computation

Sample solution for quiz of Lab Sheet 1

Machine 1.Q Construct a FA using the VTM that accepts the language L = {w : w $in$ {a,b}*, w does not begin with ab}.

One possible solution is a finite automaton M written formally as M = {Q, $Sigma$ , $delta$ , q₀, F} = {{97, 01, 98, 99}, {a, b}, $delta$ , 97, {97, 98, 99}}, where the function $delta$ formatted appropriately for the VTM is

#Si,R, Sf, W, M #-------------- 97, a, 99, a, R 97, b, 98, b, R 99, b, 01, b, R 01, a, 01, a, R 01, b, 01, b, R 98, a, 98, a, R 98, b, 98, b, R 99, a, 98, a, R