FOLA-demo38.html

Right-Quotient Languages

> ###########
### Procedure to find right quotient of 2 languages
###########
main := proc( dfa1, dfa2 )
local qdfa, i, dfaI, dfaInteX;

######
## The right quotient is defined by a DFA which is exactly the
## same as that for the first language, except for the set of final states
######
qdfa := [dfa1[1],dfa1[2],dfa1[3],dfa1[4],{}];

######
## For every internal state in the first DFA
######
for i in dfa1[1] do
   #####
   ## Create a DFA exactly like the first DFA but with that state
   ## as the starting state
   #####
   dfaI := [dfa1[1],dfa1[2],dfa1[3],i,dfa1[5]];

   #####
   ### Create a DFA that is the describes the language that is the
   ### intersection of that described by the above DFA and the
   ### second language
   #####
   dfaInteX := createIntersection( dfaI, dfa2 );

   #####
   ## For debugging
   # print( dfaInteX );
   #####

   ####
   ## Check if the resulting DFA describes a NULL language
   ####
   if( checkIfEmpty( dfaInteX ) = 0 ) then
     ####
     ## If it doesnot, then add this state to the set of final states
     ####

     ####
     ## For debugging only
     # print( "Not Empty" );
     ####
     qdfa[5] := qdfa[5] union {i};
   else
     ####
     ## For debugging only
     # print( "Empty" );
     ####
   fi;
od;
print( "The right quotient is described by:", qdfa );
end:

> ######
## Procedure to create a DFA that describes the intersection of
## of two regular languages
######
createIntersection := proc( FirstDfa, SecondDfa )
local IntersectDfa, IntStatesInt, FinStateInt, i, j, AlphaInt, InitInt;

IntStatesInt := {};
FinStateInt := {};

####
## Set of internal states is Q1 x Q2
####
for i in FirstDfa[1] do
for j in SecondDfa[1] do
   IntStatesInt := IntStatesInt union {[i, j]};
od;
od;

### Set of alphabets is the same
AlphaInt := FirstDfa[2];

######
## Initial State is [q0 , q0 ]
##                     1    2
######
InitInt := [FirstDfa[4], SecondDfa[4]];

######
## Set of Final States is F1 x F2
######
for i in FirstDfa[5] do
for j in SecondDfa[5] do
   FinStateInt := FinStateInt union {[i, j]};
od;
od;

#####
## Add delta function as follows:
## delta( [qi, qj], a ) = [delta1( qi, a ), delta2( qj, a )]
#####
for i in IntStatesInt do
for j in AlphaInt do
   delta3(i,j) := [FirstDfa[3](i[1],j), SecondDfa[3](i[2],j)];
od;
od;

## Package it and return
IntersectDfa := [IntStatesInt, AlphaInt, delta3, InitInt, FinStateInt];
RETURN( IntersectDfa );
end:

> ######
## Check if the language describe by the DFA is empty
######
checkIfEmpty := proc( myDfa )
local tempList, tempCnt, i, j, ReachStates, UnReachable;

####
## The idea is to see if all final states are inaccessible
####
tempList := [myDfa[4]];         # Start with the initial state
tempCnt := 1;
i := 0;
do                              # For each state that is accessible
i := i + 1;
for j from 1 to nops(myDfa[2]) do          # Check transition on every symbol
   ###
   # If a new state becomes reachable.. add it to the list
   ###
   if not member( myDfa[3](tempList[i], myDfa[2][j]), tempList ) then
     tempList := [op(tempList), myDfa[3](tempList[i], myDfa[2][j])];
     tempCnt := nops(tempList);
   fi;
od;
if i = tempCnt then
   break;
fi;
od;
####
## For debugging
#print( "tempList:", tempList );
####
ReachStates := {op(tempList)};              # These are all the reachable states
UnReachable := myDfa[1] minus ReachStates; # These are all the unreachable states
if myDfa[5] union UnReachable = UnReachable then
## All final states are unreachable ==> NULL language
RETURN( 1 );
fi;

## Atleast one final state reachable ==> Non-NULL language
RETURN( 0 );
####
## For debugging
#print( ReachStates );
####
end: