Dzidrais avots

--
-- Author: Pēteris Pakalns
-- Apl.nr: pp15008
--
-- finite state nondeterministic automaton with epsilon transition
-- lua dzidrais-avots.lua
--

-- constants
print_additional_info = true
eps = "_eps"
input_filename = "avots.txt"

-- ============================================================
-- UTILITY functions

-- Split string into individual words ,
-- eg. "asds asdf asdf asdf\n" => {"asds","asdf","asdf","asdf"}
function getWordArray( str )
    local W, i = {}, 1
    while i do
        local s, e = string.find(str, "%w+", i)
        if s then
            table.insert( W, string.sub(str, s, e))
            i = e + 1
        else i =nil end
    end
    return W
end

-- Create set from array
function getSet( array )
    local Q = {}
    for i,v in ipairs( array ) do Q[ v ]=true end
    return Q
end

-- return set union
function setUnion( A, B )
    A, B, R = (A or {}), (B or {}), {}
    for i,v in pairs( A ) do
        if ( v ) then R[ i ] = true end
    end
    for i,v in pairs( B ) do
        if ( v ) then R[ i ] = true end
    end
    return R
end

function setAppend( A, ...)
    arg={...}
    for key, B in ipairs(arg) do
        B = B or {}
        for elem,_ in pairs( B ) do
            A[ elem ] = true;
        end
    end
end

-- return set intersection
function setIntersection( A, B )
    A, B, R = A or {}, B or {}, {}
    for i,v in pairs( A ) do
        if ( v and B[ i ] ) then R[ i ] = true end
    end
    return R
end

-- Check if set is empty
function isEmptySet( A )
    for i, v in pairs( A or {} ) do
        if ( v ) then return false end
    end
    return true
end

-- return set string representation
function strSet( A )
    local str, semicol="",false
    str=str.." {"
    for i,v in pairs( A ) do
        if ( v ) then
            str=str..((semicol) and "; "..i or " "..i )
        end
        semicol=true
    end
    str=str.."} "
    return str
end

-- return two element cortege set string representation
function strCortegeSet( A )
    str=""
    for i, v in pairs( A ) do
        for l, m in pairs( v ) do
            for x,y in pairs( m ) do
                if ( y ) then
                    str = str .. "("..i..";"..l.."):"..x.."; "
                end
            end
        end
    end
    return " { "..str:sub(1,-2).." } "
end

-- #################################################
-- Automaton functions

-- load finite state nondeterministic automaton with epsilon transition
function load_data( filename )

    local file = io.open( filename, "r" )

    local Q = getSet( getWordArray( file:read() ) );
    local E = getSet( getWordArray( file:read() ) );
    local q0 = getSet( getWordArray( file:read() ) );
    local F = getSet( getWordArray( file:read() ) );

    local delta = {}
    for i,v in pairs( Q ) do delta[ i ] = {} end

    repeat
        local line = file:read()
        if line then
            local word_array, let, next_state, state= getWordArray( line )
            if ( #word_array < 2 ) then break end
            if ( #word_array == 2 ) then
                state, let, next_state = word_array[ 1 ], eps, word_array[ 2 ];
            else
                state, let, next_state = word_array[ 1 ], word_array[ 2 ], word_array[ 3 ];
            end
            if ( delta[ state ][ let ] == nil ) then delta[ state ][ let ] = {} end
            delta[ state ][ let ][ next_state ] = true;
        end
    until (line==nil)

    file:close();

    return Q, E, delta, q0, F
end

-- Check all state transitivity (eps)
-- delta[ state ][ eps ] = TS( state )
function explore_forward( delta, state )
    local stack = {}
    for to, check in pairs( delta[ state ][ eps ] or {} ) do
        if ( check ) then table.insert( stack, to ) end
    end

    while ( #stack > 0 ) do
        local act_state = table.remove( stack )
        for to, check in pairs( delta[ act_state ][ eps ] or {} ) do
            if ( check ) then
                if ( not delta[ state ][ eps ][ to ] ) then
                    delta[ state ][ eps ][ to ] = true;
                    table.insert( stack, to );
                end
            end
        end
    end
end

-- epsilon
function epsLetter( delta, q_now )
    local q_upd = {}
    for state,_ in pairs( q_now or {} ) do
        setAppend( q_upd, delta[ state ][ eps ] )
    end
    setAppend( q_now, q_upd )
end


-- Returns if input word is accepted
function deltaR( Q, E, delta, q_set, F, input )

    local q_now, q_next, last = setUnion( q_set, {} ), {}, 0

    if ( input==nil ) then input="" end

    for i=1,#input do

        local let = input:sub(i,i)
        if ( isEmptySet( q_now ) or not E[ let ] ) then break end

        epsLetter( delta, q_now )

        for state,_ in pairs( q_now ) do
            setAppend( q_next, delta[ state ][ let ] )
        end

        q_now, q_next, last = q_next, {}, i;
    end

    -- epsilon letter moves
    epsLetter( delta, q_now );

    local good_states = setIntersection( F, q_now );

    if ( print_additional_info ) then
        print("  Apstrādāts vārda prefiks : \""..input:sub( 1, last ).."\"\n");
        print("     \t      Q(|w+eps|) =\t"..strSet( q_now ) )
        print("     \tF inters. Q(|w|) =\t"..strSet( good_states ) )
    end

    return not isEmptySet( good_states );
end

-- READ DATA

local Q, E, delta, q_set, F = load_data( input_filename )

if ( print_additional_info ) then
    print("\n########## Authomaton ################\n");
    print("         Q =\t"..strSet( Q  ) )
    print("  Alphabet =\t"..strSet( E  ) )
    print("     delta =\t"..strCortegeSet( delta ) )
    print("      {q0} =\t"..strSet( q_set ) )
    print("         F =\t"..strSet( F  ) )
end

-- UPDATE DATA

for i,v in pairs(Q) do explore_forward( delta, i ) end

if ( print_additional_info ) then
    print("\n    delta\"eps =\t"..strCortegeSet( delta ) )
    io.write("\n\n");
end

-- User input

while ( true ) do
    if print_additional_info then io.write("   Lūdzu ievadiet meklējamo vārdu(w): "); end
    input = io.read()
    io.write("\n\t\tAtbilde : "..(deltaR( Q, E, delta, q_set, F, input ) and "True" or "False" ).." ! \n\n");
end