class NFAtoDFA

#read file input
gi = File.foreach(‘example8.txt’).map {|line| line.split(/\s,\n/)}
start = gi20
finish = gi3
states = gi0
symbols = gi1
transition = Array.new(states.length){Array.new(symbols.length)}
for a in 0..(states.length-1)
for b in 0..(symbols.length-1)
transitionab = gia+4b
end
end

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

#create transition function (t)
tfunction = Array.new(states.length){Array.new(symbols.length-1)}
for a in 0..(states.length-1)
k = symbols.length-1
#check lambda
lambdagive = Array.new
lambdagive =transitionak.split(“:”)
for b in 0..(symbols.length-2)
substates = Array.new()
subtran = String.new
substates = transitionab.split(“:”)
#puts substates
for c in 0..(substates.length-1)
subtran = subtran + “:” + substatesc
end

#check transition from lambda
if (lambdagive.empty? == false)
for x in lambdagive
if (x != “nil”)
if (transitionstates.index(x)b != “nil”)
subtran = subtran + “:” + transitionstates.index(x)b
end
end
end
end
tfunctionab = subtran
end
end
puts tfunction.to_a.map(&:inspect)

#construct DFA from NFA
transDFA = Array.new(10){Array.new(symbols.length-1)}
nstates = Array.new()
#start from q0
#check from tfunction table
i = 1
row = 0
now = 0
nstates0 = “:”+start
nfnish = Array.new()
until i == 0
substates = nstatesnow.chomp.split(‘:’).reject(&:empty?)
substates.delete(‘nil’)
substates = substates.uniq
for j in 0..(symbols.length-2)
newstates = “”
for k in substates
#puts k
#check each states in tfunction
it = states.index(k)
if (tfunctionitj != “:nil” )
newstates = newstates + tfunctionitj
end
end
newstates.slice! “:nil”
aa = Array.new
aa = newstates.split(“:”)
aa= aa.uniq
aa = aa.sort
newstates = aa.join(“:”)
ba = nstates.include? newstates
if ((ba == false))
nstatesrow+1 = newstates
ca = (aa & finish).any?
if ((ca == true))
nfnish.push(newstates)
end
i = i + 1
row = row + 1
end
transDFAnowj = newstates
end
i = i – 1
now = now + 1
end
for x in transDFA
for y in x
z = y == “”
if (z == true)
y.replace(“qn”)
end
end
end
open(‘example2.txt’, ‘w’) do |f|
f.puts nstates.join(‘,’)
f.puts (symbols-“lm”).join(‘,’)
f.puts “:”+start
f.puts nfnish.join(‘,’)
transDFA.each{ |inner| f.puts inner.join(‘,’)}
end
end