# -*- coding: utf-8 -*-
"""**Several combined operations for DFAs**
Combined operations
.. *Authors:* Rogério Reis & Nelma Moreira
.. versionadded: 0.9.4
.. *This is part of FAdo project* http://fado.dcc.fc.up.pt.
.. *Copyright:* 1999-2014 Rogério Reis & Nelma Moreira {rvr,nam}@dcc.fc.up.pt
.. This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License as published
by the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
675 Mass Ave, Cambridge, MA 02139, USA."""
from fa import *
from common import *
[docs]def starConcat(fa1, fa2, strict=False):
""" Star of concatenation of two languages: (L1.L2)*
:param DFA f a1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Yuan Gao, Kai Salomaa, and Sheng Yu. 'The state complexity of two combined operations: Star of catenation and
star of reversal'. Fundamenta Informaticae, 83:75–89, Jan 2008."""
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
if len(d1.States) > 1 and len(d2.States) == 1:
if d2.finalP(d2.Initial):
new = d1.addState()
iold = d1.Initial
d1.setInitial(new)
d1.addFinal(new)
for sym in d1.Sigma:
d1.addTransition(new, sym, d1.delta[iold][sym])
for s in d1.Final:
d1.delta[s][sym] = s
return d1
c = DFA()
c.setSigma(d1.Sigma)
s0, s1 = c.addState(0), c.addState(1)
c.setInitial(s0)
c.addFinal(s0)
for sym in c.Sigma:
c.addTransition(s0, sym, s1)
c.addTransition(s1, sym, s1)
return c
if len(d2.States) > 1 and len(d1.States) == 1:
if d1.finalP(d1.Initial):
c = NFA()
c.setSigma(d2.Sigma)
c.States = d2.States[:]
p1 = c.addState(0)
p2 = c.addState(1)
c.addInitial(p1)
c.setFinal(list(d2.Final))
for sym in c.Sigma:
c.addTransition(p1, sym, d2.delta[d2.Initial][sym])
c.addTransition(p1, sym, p2)
c.addTransition(p2, sym, d2.delta[d2.Initial][sym])
c.addTransition(p2, sym, p2)
for s in d2.States:
c.addTransition(s, sym, d2.delta[s][sym])
return c.toDFA()
# Epsilon automaton
c = DFA()
c.setSigma(d1.Sigma)
s0, s1 = c.addState(0), c.addState(1)
c.setInitial(s0)
c.addFinal(s0)
for sym in c.Sigma:
c.addTransition(s0, sym, s1)
c.addTransition(s1, sym, s1)
return c
c = DFA()
c.setSigma(d1.Sigma)
lStates = []
i = c.addState("initial")
c.setInitial(i)
c.addFinal(i)
lStates.append(i)
for sym in c.Sigma:
s1 = {d1.evalSymbol(d1.Initial, sym)}
s2 = set([])
# Z1
if s1 & d1.Final != set([]):
s2.add(d2.Initial)
if d2.finalP(d2.Initial):
s1.add(d1.Initial)
if d1.finalP(d1.Initial):
s2.add(d2.evalSymbol(d2.Initial, sym))
# Z2
if s2 & d2.Final != set([]):
s1.add(d1.Initial)
s2.add(d2.Initial)
stn = (s1, s2)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[1] & d2.Final != set([]):
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(i, sym, new)
if len(c.States) == 1:
return c
j = 1
while True:
stu = lStates[j]
s = c.stateIndex(stu)
for sym in c.Sigma:
stn = (d1.evalSymbolL(stu[0], sym),
d2.evalSymbolL(stu[1], sym))
if stn[0] & d1.Final != set([]):
stn[1].add(d2.Initial)
if d2.finalP(d2.Initial):
stn[0].add(d1.Initial)
if stn[1] & d2.Final != set([]):
stn[0].add(d1.Initial)
if d1.finalP(d1.Initial):
stn[1].add(d2.Initial)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[1] & d2.Final != set([]):
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(lStates) - 1:
break
else:
j += 1
return c
[docs]def concatWStar(fa1, fa2, strict=False):
"""Concatenation combined with star: (L1.L2*)
:param DFA fa1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. 'State complexity of two combined operations: Reversal-catenation
and star-catenation'. CoRR, abs/1006.4646, 2010."""
if len(fa1.States) == 0 or len(fa1.Final) == 0 or len(fa2.States) == 0 or len(fa2.Final) == 0 or \
(len(fa1.States) == 1 and len(fa2.States) > 0):
return fa1
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
if len(d2.Final) == 1 and d2.finalP(d2.Initial):
return d1.concat(d2)
c = DFA()
c.setSigma(d1.Sigma)
lStates = []
if d1.finalP(d1.Initial):
s2 = 1
else:
s2 = 0
i = (d1.Initial, s2, set([]))
lStates.append(i)
j = c.addState(i)
c.setInitial(j)
if s2 == 1:
c.addFinal(j)
F0 = d2.Final - {d2.Initial}
while True:
stu = lStates[j]
s = c.stateIndex(stu)
for sym in c.Sigma:
s1 = d1.evalSymbol(stu[0], sym)
if d1.finalP(s1):
s2 = 1
else:
s2 = 0
if stu[1] == 1:
s3 = {d2.evalSymbol(d2.Initial, sym)}
# correction
if s3 & F0 != set([]):
s3.add(d2.Initial)
else:
s3 = set([])
s4 = d2.evalSymbolL(stu[2], sym)
if s4 & F0 != set([]):
s4.add(d2.Initial)
stn = (s1, s2, s3.union(s4))
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[1] == 1 or (d2.Final & stn[2] != set([])):
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(lStates) - 1:
break
else:
j += 1
return c
[docs]def starWConcat(fa1, fa2, strict=False):
"""Star combined with concatenation: (L1*.L2)
:param DFA fa1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Bo Cui, Yuan Gao, Lila Kari, and Sheng Yu. 'State complexity of catenation combined with star and reversal'.
CoRR, abs/1008.1648, 2010"""
if len(fa1.States) == 0 or len(fa1.Final) == 0 or len(fa2.States) == 0 or len(fa2.Final) == 0 \
or (len(fa2.States) == 1 and len(fa1.States) > 0):
return fa2
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
c = DFA()
c.setSigma(d1.Sigma)
if len(d1.Final) == 1 and d1.finalP(d1.Initial):
i = (d1.Initial, {d2.Initial})
j = c.addState(i)
c.setInitial(j)
if i[1] & d2.Final != set([]):
c.addFinal(j)
while True:
s = c.States[j]
for sym in c.Sigma:
stn = (d1.evalSymbol(s[0], sym), d2.evalSymbolL(s[1], sym))
if d1.initialP(s[0]):
stn[1].add(d2.Initial)
try:
new = c.addState(stn)
if stn[1] & d2.Final != set([]):
c.addFinal(new)
except DuplicateName:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(c.States) - 1:
break
else:
j += 1
return c
# |Final1|>1
j = c.addState(({d1.Initial}, {d2.Initial}))
c.setInitial(j)
if d2.finalP(d2.Initial):
c.addFinal(j)
while True:
s = c.States[j]
for sym in c.Sigma:
stn = (d1.evalSymbolL(s[0], sym), d2.evalSymbolL(s[1], sym))
if stn[0] & d1.Final != set([]):
stn[1].add(d2.Initial)
stn[0].add(d1.Initial)
try:
new = c.addState(stn)
if stn[1] & d2.Final != set([]):
c.addFinal(new)
except DuplicateName:
new = c.stateIndex(stn)
c.addTransition(j, sym, new)
if j == len(c.States) - 1:
break
else:
j += 1
return c
[docs]def starDisj(fa1, fa2, strict=False):
"""Star of Union of two DFAs: (L1 + L2)*
:param DFA fa1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Arto Salomaa, Kai Salomaa, and Sheng Yu. 'State complexity of combined operations'. Theor. Comput. Sci.,
383(2-3):140–152, 2007."""
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
c = DFA()
c.setSigma(NSigma)
lStates = []
if d1.Initial in d1.Final or d2.Initial in d2.Final:
i = ({d1.Initial}, {d2.Initial})
else:
i = "initial"
lStates.append(i)
j = c.addState(i)
c.setInitial(j)
c.addFinal(j)
for sym in c.Sigma:
stn = ({d1.evalSymbol(d1.Initial, sym)}, {d2.evalSymbol(d2.Initial, sym)})
if stn[0] & d1.Final or stn[1] & d2.Final:
stn[0].add(d1.Initial)
stn[1].add(d2.Initial)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[0] & d1.Final or stn[1] & d2.Final:
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(j, sym, new)
if len(lStates) < 2:
return c
j = 1
while True:
stu = lStates[j]
s = c.stateIndex(stu)
for sym in c.Sigma:
stn = (d1.evalSymbolL(stu[0], sym), d2.evalSymbolL(stu[1], sym))
if stn[0] & d1.Final or stn[1] & d2.Final:
stn[0].add(d1.Initial)
stn[1].add(d2.Initial)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[0] & d1.Final or stn[1] & d2.Final:
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(lStates) - 1:
break
else:
j += 1
return c
[docs]def starInter0(fa1, fa2, strict=False):
"""Star of Intersection of two DFAs: (L1 & L2)*
:param DFA fa1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Arto Salomaa, Kai Salomaa, and Sheng Yu. 'State complexity of combined operations'. Theor. Comput. Sci.,
383(2-3):140–152, 2007."""
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
c = DFA()
c.setSigma(NSigma)
lStates = []
if d1.finalP(d1.Initial) and d2.finalP(d2.Initial):
i = ({d1.Initial}, {d2.Initial})
else:
i = "initial"
lStates.append(i)
j = c.addState(i)
c.setInitial(j)
c.addFinal(j)
for sym in c.Sigma:
stn = ({d1.evalSymbol(d1.Initial, sym)}, {d2.evalSymbol(d2.Initial, sym)})
if stn[0] & d1.Final and stn[1] & d2.Final:
stn[0].add(d1.Initial)
stn[1].add(d2.Initial)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[0] & d1.Final and stn[1] & d2.Final:
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(j, sym, new)
if len(lStates) < 2:
return c
j = 1
while True:
stu = lStates[j]
s = c.stateIndex(stu)
for sym in c.Sigma:
stn = (d1.evalSymbolL(stu[0], sym), d2.evalSymbolL(stu[1], sym))
if stn[0] & d1.Final and stn[1] & d2.Final:
stn[0].add(d1.Initial)
stn[1].add(d2.Initial)
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
if stn[0] & d1.Final and stn[1] & d2.Final:
c.addFinal(new)
else:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(lStates) - 1:
break
else:
j += 1
return c
[docs]def starInter(fa1, fa2, strict=False):
"""Star of Intersection of two DFAs: (L1 & L2)*
:param DFA fa1: first automaton
:param DFA fa2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA """
if strict and fa1.Sigma != fa2.Sigma:
raise DFAdifferentSigma
NSigma = fa1.Sigma.union(fa2.Sigma)
d1, d2 = fa1.dup(), fa2.dup()
d1.setSigma(NSigma)
d2.setSigma(NSigma)
d1.complete()
d2.complete()
c = DFA()
c.setSigma(NSigma)
lStates = []
if d1.finalP(d1.Initial) and d2.finalP(d2.Initial):
i = {(d1.Initial, d2.Initial)}
else:
i = "initial"
lStates.append(i)
j = c.addState(i)
c.setInitial(j)
c.addFinal(j)
for sym in c.Sigma:
stn = {(d1.evalSymbol(d1.Initial, sym), d2.evalSymbol(d2.Initial, sym))}
for sub in stn:
if d1.finalP(sub[0]) and d2.finalP(sub[1]):
stn.add((d1.Initial, d2.Initial))
break
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
for sub in stn:
if d1.finalP(sub[0]) and d2.finalP(sub[1]):
c.addFinal(new)
break
else:
new = c.stateIndex(stn)
c.addTransition(j, sym, new)
if len(lStates) < 2:
return c
j = 1
while True:
stu = lStates[j]
s = c.stateIndex(stu)
for sym in c.Sigma:
stn = set([])
flag = 1
for sub in stu:
one = (d1.evalSymbol(sub[0], sym), d2.evalSymbol(sub[1], sym))
stn.add(one)
if flag == 1 and d1.finalP(one[0]) and d2.finalP(one[1]):
stn.add((d1.Initial, d2.Initial))
flag = 0
if stn not in lStates:
lStates.append(stn)
new = c.addState(stn)
for sub in stn:
if d1.finalP(sub[0]) and d2.finalP(sub[1]):
c.addFinal(new)
break
else:
new = c.stateIndex(stn)
c.addTransition(s, sym, new)
if j == len(lStates) - 1:
break
else:
j += 1
return c
[docs]def disjWStar(f1, f2, strict=True):
"""Union with star: (L1 + L2*)
:param DFA f1: first automaton
:param DFA f2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Yuan Gao and Sheng Yu. 'State complexity of union and intersection combined with star and reversal'. CoRR,
abs/1006.3755, 2010."""
if strict and f1.Sigma != f2.Sigma:
raise DFAdifferentSigma
return f1.star() | f2
[docs]def interWStar(f1, f2, strict=True):
"""Intersection with star: (L1 & L2*)
:param DFA f1: first automaton
:param DFA f2: second automaton
:param bool strict: should the alphabets be necessary equal?
:rtype: DFA
.. seealso::
Yuan Gao and Sheng Yu. 'State complexity of union and intersection combined with star and reversal'. CoRR,
abs/1006.3755, 2010."""
if strict and f1.Sigma != f2.Sigma:
raise DFAdifferentSigma
return f1.star() & f2