HaLeX-1.2.5: HaLeX_lib/Language/HaLex/Sentences.hs
-----------------------------------------------------------------------------
-- |
-- Module : Language.HaLex.Sentences
-- Copyright : (c) João Saraiva 2017
-- License : LGPL
--
-- Maintainer : jas@di.uminho.pt
-- Stability : provisional
-- Portability : portable
--
-- Generation of sentences for (regular) languages defined via
-- Regular Expressions and Finite Autumata
--
-----------------------------------------------------------------------------
module Language.HaLex.Sentences ( sentencesRegExp
, sentencesNdfa
, sentencesDfa
, onePathDfa
) where
import Language.HaLex.Dfa
import Language.HaLex.Ndfa
import Language.HaLex.RegExp
import Language.HaLex.RegExp2Fa
import Language.HaLex.RegExpParser
import Language.HaLex.FaOperations
import Language.HaLex.Minimize
import Data.Maybe
import Data.List
-----------------------------------------------------------------------------
-- * Generating Sentence
-- | Generates a set of sentences of the language defined by a given
-- Regular Expression
sentencesRegExp :: Ord sy => RegExp sy -> [[sy]]
sentencesRegExp = sentencesDfa . regExp2Dfa
-- | Generates a set of sentences of the language defined by a given
-- NonDerterministic Finite Automaton
sentencesNdfa :: (Ord sy , Ord st) => Ndfa st sy -> [[sy]]
sentencesNdfa = sentencesDfa . minimizeDfa . ndfa2dfa
-- | Generates a set of sentences of the language defined by a given
-- Deterministic Finite Automaton.
--
-- It computes a set of paths starting from the start state and ending
-- in an accepting state, which include all transitions/edges of the
-- automaton.
--
-- This function does not computes the smallest set (of paths/sentebces),
-- as computed by the "Chinese Postman Problem"
--
-- Function written by MSc student José Nuno Macedo (72424)
-- in the context of the 2016/17 edition of the course
-- "Analysis and Testing of Software", MIEI, Univ. Minho.
--
sentencesDfa :: (Ord st, Eq sy, Ord sy) => Dfa st sy -> [[sy]]
sentencesDfa = nub . sentencesDfa'
-- | This auxiliar function uses the transition table computed from the
-- given automaton to generate a finite set of sentences the the
-- language.
sentencesDfa' :: (Ord st, Ord sy) => Dfa st sy -> [[sy]]
sentencesDfa' d = sentences d tt tt
where tt = transitionTableDfa d
-- | This function generates all paths (corresponding to valid sentences
-- of the language) that cover all transitions of the finite automaton.
-- The transition table serves two purposes when calling this function:
-- - to know the transitions of the automaton
-- - to serve has the state recording all transitions not used (yet)
-- (in the begining this list should be the full transition
-- table of the dfa, and the function terminates when this
-- list is empty: no more tarnsitions need to be covered)
sentences :: (Ord st, Ord sy)
=> Dfa st sy -- ^ Automaton
-> [(st, sy, st)] -- ^ Dfa's Transition Table
-> [(st, sy, st)] -- ^ Table with transitions to be used
-> [[sy]] -- ^ List of sentences
sentences _ _ [] = []
sentences d@(Dfa _ _ s z _) tt mustUse = sys ++ rec_call
where
-- First, we compute all paths from the start state to each state
-- in the set of final sates. Each path produces the list of
-- transitions that need to be used and the sentence formed by
-- that path
(newMustUses, sys) = unzip [onePath tt mustUse [] fs' s | fs' <- z ]
-- The lists of transitions to be used (produced by each path)
-- is merged into a sinle list of transitions still to be used
newMustUse = foldr1 intersect newMustUses
-- Recursive call with the new list os transitions still to be used.
-- note that if the new transitions (to be used) are the same to the
-- received ones, no progress was made. Thus no (non-finishing)
-- recursive call is performed.
rec_call = if newMustUse == mustUse
then []
else (sentences d tt newMustUse)
-- | This function computes one path from a given start state to a given final
-- state. The function does not repeat transitions. This function
-- "walks backwards": it starts from the final state back to the start one.
--
-- It receives the Dfa's transition table (tt), the table with the
-- transitions that Can Be Used (cbu), the labels of the transitions used
-- thus far (sys), the final state (ft), the start state (st).
-- It returns a pair:
-- the transitions that were not used in this path
-- the list of labels used in the path
onePath :: (Eq sy, Eq st)
=> [(st, sy, st)] -- ^ Dfa's Transition Table
-> [(st, sy, st)] -- ^ Table with transitions to be used
-> [sy] -- ^ list of labels (used so far)
-> st -- ^ final state
-> st -- ^ start state
-> ([(st, sy, st)] , [sy])
onePath tt cbu sys ft st
| ft == st = (cbu, sys)
| otherwise = onePath tt (delete k cbu) (symbol:sys) before_f st
-- at each recursive call it performs a backwards step
-- the new final state is the origin of the chosen transition
-- (where the previous final state (ft) is the destination).
-- The transition used is deleted from can be used.
-- The initial state (st) and trans. table (tt) do not change.
where
-- computing the lists of transitions with the final state (ft)
-- as destination: both for the trans. table and the can be used
-- transitions
priorityList = filter (\(a,_,c) -> c == ft) cbu
p2 = filter (\(a, _, c) -> a /= c && c == ft) tt
-- selects the transition from the computed lsits, prefering
-- the transitions coming from the can be used trable.
k@(before_f, symbol, _) = head $ priorityList ++ p2
-- | This function computes one sentence of the language defined by
-- a deterministic fininte automaton
onePathDfa :: (Ord st, Ord sy) => Dfa st sy -> [sy]
onePathDfa dfa@(Dfa v q s z d) = snd $ onePath ttdfa ttdfa [] (head z) s
where ttdfa = transitionTableDfa dfa