Regular languages and finite automata

2020-12-10

What are the languages that can be described by finite automata?

slides
lecture
```
  
```

Implementing algebraic operations on languages at the machine level

We have three simple implementations of NFAs.

‘concrete’ (everything is a list)

data NFA_List q sigma =
  NFA_List
  [q] -- the set of initial states
  [(q,sigma,q)] -- the transition relation
  [q] -- the set of final states

‘abstract’ (everything is a function)

data NFA_Func q sigma =
  NFA_Func
  (q -> Bool) -- initial states
  (q -> sigma -> q -> Bool) -- transitions
  (q -> Bool) -- final states

‘mixed’

data NFA_Mixed q sigma =
  NFA_Mixed
  [q] -- initial states
  (q -> Maybe sigma -> [q]) -- transitions
  (q -> Bool) -- final states

These representations contain the same information, but they differ in their constructivity.

Complement

The idea is to swap out final and non-final states.

concrete

compList :: Eq q => NFA_List q sigma -> NFA_List q sigma
compList (NFA_List inits trans finals) = NFA_List inits trans newFinals
  where
    newFinals = allStates \\ finals
    allStates = nub (inits ++ concat [[q,q'] | (q,_,q') <- trans])

abstract

compFunc :: NFA_Func q sigma -> NFA_Func q sigma
compFunc (NFA_Func inits trans finals)  = NFA_Func inits trans (not . finals)

mixed

compMixed :: NFA_Mixed q sigma -> NFA_Mixed q sigma
compMixed (NFA_Mixed inits trans finals) = NFA_Mixed inits trans (not . finals)

Union and Intersection

The idea is to walk through both machines simultaneously

concrete

xProdList :: (Eq q,Eq sigma) => NFA_List q sigma -> NFA_List q' sigma -> ((q,q') -> Bool) -> NFA_List (q,q') sigma
xProdList (NFA_List inits trans finals) (NFA_List inits' trans' finals') newFinalTest =
  NFA_List [(q,q') | q <- inits, q' <- inits']
           [((q1,q1'),a,(q2,q2')) | (q1,a,q2) <- trans,
                                    (q1',b,q2') <- trans',
                                     a == b]
           (filter newFinalTest [(q,q') | q <- allStates, q' <- allStates'])
  where
    allStates = nub (inits ++ concat [[q,q'] | (q,_,q') <- trans])
    allStates' = nub (inits' ++ concat [[q,q'] | (q,_,q') <- trans'])

unionList nfa1@(NFA_List _ _ finals) nfa2@(NFA_List _ _ finals') = xProdList nfa1 nfa2 (\(q,q') -> elem q finals || elem q' finals')
intersectList nfa1@(NFA_List _ _ finals) nfa2@(NFA_List _ _ finals') = xProdList nfa1 nfa2 (\(q,q') -> elem q finals && elem q' finals')

abstract

xProdFunc :: NFA_Func q sigma -> NFA_Func q' sigma -> ((q,q') -> Bool) -> NFA_Func (q,q') sigma
xProdFunc (NFA_Func inits trans finals) (NFA_Func inits' trans' finals') =
  NFA_Func (\ (q,q') -> inits q && inits' q')
           (\ (q1,q1') a (q2,q2') -> trans q1 a q2 && trans' q1' a q2')
unionFunc nfa@(NFA_Func _ _ finals)  nfa'@(NFA_Func _ _ finals') =
  xProdFunc nfa nfa' (\ (q,q') -> finals q || finals' q')
intersectFunc nfa@(NFA_Func _ _ finals)  nfa'@(NFA_Func _ _ finals') =
  xProdFunc nfa nfa' (\ (q,q') -> finals q && finals' q')

mixed

xProdMixed :: NFA_Mixed q sigma -> NFA_Mixed q' sigma -> ((q,q') -> Bool) -> NFA_Mixed (q,q') sigma
xProdMixed (NFA_Mixed inits trans finals) (NFA_Mixed inits' trans' finals') =
  NFA_Mixed [(q,q') | q <- inits, q' <- inits']
           (\ (q1,q1') a -> (trans q1 a, trans' q1' a))
unionMixed nfa@(NFA_Mixed _ _ finals)  nfa'@(NFA_Mixed _ _ finals') =
  xProdMixed nfa nfa' (\ (q,q') -> finals q || finals' q')
intersectMixed nfa@(NFA_Mixed _ _ finals)  nfa'@(NFA_Mixed _ _ finals') =
  xProdMixed nfa nfa' (\ (q,q') -> finals q && finals' q')

Reversal

The idea is to begin at the final states, to end at the start states, and to take transitions in the reverse direction.

concrete

revList :: NFA_List q sigma -> NFA_List q sigma
revList (NFA_List inits trans finals) = NFA_List finals revTrans inits
  where
    revTrans = [(q',a,q) | (q,a,q') <- trans]

abstract

revFunc :: NFA_Func q sigma -> NFA_Func q sigma
revFunc (NFA_Func inits trans finals)  = NFA_Func finals revTrans inits
  where
    revTrans q a q' = trans q' a q

mixed

revMixed :: Eq q => NFA_Mixed q sigma -> NFA_Mixed q sigma
revMixed (NFA_Mixed inits trans finals) = NFA_Mixed undefined undefined (\q -> elem q inits)
  where
    newInits = [q | q <- stateGenerator, finals q]
    newTrans q a = [q' | q' <- stateGenerator, elem q (trans q' a)]
    stateGenerator = undefined

To define revMixed we need some way of enumerating all states of the machine. If we enriched the datatype NFA_Mixed by adding a list of all states, we could then define this function.