# -*- coding: utf-8 -*-
"""Code theory module
.. versionadded:: 1.0
.. *Authors:* Rogério Reis, Nelma Moreira & Stavros Konstantinidis
.. *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."""
import copy
import reex
from common import *
import fio
from transducers import SFT, infixTransducer, prefixTransducer, suffixTransducer, outfixTransducer, hypercodeTransducer
import fa
import fl
def fixedHierSubset(x, y):
""" Returns whether x==y, or the fixed property with name x is a subset of y
Currently (Jan 2015) the fixed properties names are 'UD_codes',
'Prefix_codes', 'Suffix_codes', 'Infix_codes', 'Outfix_codes', 'Hypercodes'
:param tuple x: first argument
:param tuple y: second argument
:rtype: bool"""
if x == y:
return True
if x[0] != 'Fixed' or y[0] != 'Fixed':
return False
if x[1] == 'Hypercodes' or y[1] == 'UD_codes':
return True
if x[1] == 'UD_codes' or y[1] == 'Hypercodes':
return False
if x[1] == 'Infix_codes':
if y[1] == 'Outfix_codes':
return False
else:
return True
if x[1] == 'Outfix_codes':
if y[1] == 'Infix_codes':
return False
else:
return True
if y[1] == 'Infix_codes' or y[1] == 'Outfix_codes':
return False
if x[1] == y[1]:
return True
else:
return False
def isSubclass(p1, p2):
"""Which property (language class) is a subclass of the other (if any).
It returns 1 if p1 is a subclass of p2; 2 if p2 is a subclass of p1;
3 if they are equal; 0 otherwise
:param IPTProp p1: an input preserving transducer property
:param IPTProp p2: an input preserving transducer property
:rtype: int"""
def _lessEqualID(first, second):
""" Returns whether the property with ID X is a subset of that with ID Y.
This is the case when X has a subset X1, say, such that each property named
in X1 is a subset of some property named in Y
:param set first: first argument
:param set second: second argument
:rtype: bool"""
yl = [y for y in second]
ydel = []
for x in first:
for y in yl:
if fixedHierSubset(x, y):
ydel.append(y)
yl = [y for y in yl if y not in ydel]
if len(yl) == 0:
return True
return False
if p1.Sigma != p2.Sigma:
return 0
if p1.ID <= p2.ID:
if p2.ID <= p1.ID:
return 3
else:
return 2
if p2.ID <= p1.ID:
return 1
if _lessEqualID(p1.ID, p2.ID):
return 1
if _lessEqualID(p2.ID, p1.ID):
return 2
return 0
def unionOfIDs(first, second):
""" Returns the "union" of the two sets: property ID X and propoerty ID Y.
The result is the set union minus any element in one set that names
a property containing a property named in the other set
:param set first: first argument
:param set second: second argument
:rtype: set"""
z = set() | first
xl = [x for x in first]
yl = [y for y in second]
while len(xl) > 0 and len(yl) > 0:
x = xl.pop()
ydel = []
for j in range(0, len(yl)):
y = yl[j]
if fixedHierSubset(x, y):
ydel.append(y)
elif fixedHierSubset(y, x):
z.add(y)
ydel.append(y)
z.remove(x)
break
else:
pass
yl = [y for y in yl if y not in ydel]
return z | set(yl)
[docs]class CodeProperty(object):
"""
.. seealso:: K. Dudzinski and S. Konstantinidis: Formal descriptions of code properties: decidability, complexity,
implementation. International Journal of Foundations of Computer Science 23:1 (2012), 67--85.
:var Sigma: the alphabet"""
def __init__(self, name, alph):
if name is None:
raise CodingTheoryError('new property must have a name')
self.Sigma = alph
self.ID = set()
if type(name) is set:
self.ID.update(name)
else:
self.ID.add(name)
@abstractmethod
def satisfiesP(self, aut):
"""Satisfaction of the property by the automaton language
:param NFA|DFA aut: the automaton
:rtype: bool"""
pass
@abstractmethod
def notSatisfiesW(self, aut):
"""Return a witness of non-satisfaction of the property by the automaton language
:param DFA|NFA aut: the automaton
:return: word witness tuple
:rtype: tuple"""
pass
@abstractmethod
def maximalP(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:param DFA|NFA aut: the automaton
:rtype: bool"""
pass
@abstractmethod
def notMaximalW(self, aut, U=None):
"""Witness of non maximality
:param DFA|NFA aut: the automaton
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:return: a witness
:rtype: str"""
pass
def pickFrom(s, ell):
"""Returns a random string of length ell over {0,1,...,s-1}
:param int s: the size of the alphabet (should be <= 10)
:param int ell: the length of the desired string
:return: a string
:rtype: str"""
random.seed()
w = ""
last_digit = s-1
for _ in range(ell):
d = random.randint(0,last_digit)
w += str(d)
return w
[docs]class IPTProp(CodeProperty):
"""Input Preserving Transducer Property
.. inheritance-diagram:: IPTProp
:var SFT Aut: the transducer defining the property
:var set Sigma: alphabet"""
def __init__(self, aut, name=None):
""" Constructor
:param SFT aut: Input preserving transducer"""
if name is None:
name = aut.codeOfTransducer()
super(IPTProp, self).__init__(name, aut.Sigma)
self.Aut = aut
def __eq__(self, other):
return isinstance(other, IPTProp) and (isSubclass(self, other)==3)
def __ne__(self, other):
return not self == other
def __and__(self, other):
""" Conjunction of two properties
:param IPTProp other: right hand operand
:rtype: IPTProp """
sub = isSubclass(self, other)
if sub == 1 or sub == 3:
return self
if isinstance(other, IATProp):
if sub == 2:
return other
nt = other.Aut.dup()
n = nt.addState()
nt.addInitial(n)
nt.addFinal(n)
for s in nt.Sigma:
nt.addTransition(n, s, s, n)
name = unionOfIDs(self.ID, other.ID)
pty = IPTProp(self.Aut | nt, name)
return pty
else:
if sub == 2:
return other
name = unionOfIDs(self.ID, other.ID)
pty = IPTProp(self.Aut | other.Aut, name)
return pty
[docs] def notSatisfiesW(self, aut):
"""Return a witness of non-satisfaction of the property by the automaton language
:param DFA|NFA aut: the automaton
:return: word witness pair
:rtype: tuple"""
u, v, w = self.Aut.inIntersection(aut).outIntersection(aut).nonFunctionalW()
if u == v:
return u, w
else:
return u, v
[docs] def satisfiesP(self, aut):
"""Satisfaction of the property by the automaton language
:param DFA|NFA aut: the automaton
:rtype: bool"""
return self.notSatisfiesW(aut) == (None, None)
[docs] def notMaximalW(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param DFA|NFA aut: the automaton
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:rtype: bool
:raises PropertyNotSatisfied: if not satisfied"""
if not self.satisfiesP(aut):
raise PropertyNotSatisfied("Property is not satisfied")
l = (self.Aut.runOnNFA(aut) | self.Aut.inverse().runOnNFA(aut) | aut).__invert__()
if U:
l = l & U.toNFA()
try:
w = l.witness()
except DFAEmptyDFA:
w = None
return w
[docs] def maximalP(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param NFA aut: the automaton
:param NFA U: Universe of permitted words (Sigma^* as default)
:rtype: bool"""
return self.notMaximalW(aut.toNFA(), U) is None
[docs] def notMaxStatW(self, aut, ell, n=2000, ov_free=False):
"""Returns a word of length ell to add into aut or None; simpler version of
function nonMaxStatFEpsW
:param NFA aut: the automaton
:param int ell: the length of the words in aut
:param int n: number of words to try
:return: a string or None
:rtype: str"""
#original
#if hasattr(self, "AutDetect"):
# b = self.AutDetect.runOnNFA(aut).trim()
#else:
# b = (self.Aut | self.Aut.inverse()).runOnNFA(aut).trim()
b = (self.Aut | self.Aut.inverse()).inIntersectionSlow(aut).toOutNFA().trim()
s = len(aut.Sigma)
# can use ell = len(aut.witness()), if ell was not given
tr = 1
while tr <= n:
w = pickFrom(s, ell)
if ov_free and not overlapFreeP(w):
continue
if not b.evalWordP(w): # == False:
return w
tr += 1
return None # in this case, tr == n+1
[docs] def makeCode(self, N, ell, s, n=2000,ov_free=False):
"""Returns an NFA and a list W of up to N words of length ell, such that the NFA
accepts W, which is an error-detecting language. The alphabet to use is
{0,1,...,s-1}. where s <= 10.
:param int N: the number of words to construct
:param int ell: the codeword length
:param int s: the alphabet size (must be <= 10)
:param int n: number of tries when needing a new word
:return: an automaton and a list of strings
:rtype: tuple"""
w = pickFrom(s, ell)
if ov_free:
while not overlapFreeP(w):
w = pickFrom(s, ell)
W = [w]
aut = fl.FL(W).toNFA()
cnt = 1
self.AutDetect = (self.Aut | self.Aut.inverse())
while cnt < N:
w = self.notMaxStatW(aut, ell, n,ov_free)
if w is None: break
W.append(w)
aut = fl.FL(W).toNFA()
cnt += 1
return aut, W
[docs] def makeCodeO(self, N, ell, s, n=2000, end=None, ov_free=False):
"""Returns an NFA and a list W of up to N words of length ell, such that the NFA
accepts W, which is an error-detecting language. The alphabet to use is
{0,1,...,s-1}. where s <= 10.
:param int N: the number of words to construct
:param int ell: the codeword length
:param int s: the alphabet size (must be <= 10)
:param int n: number of tries when needing a new word
:param Word end: a Word or None that should much the end of code words
:param Boolean ov_free: if True code words much be overlap free
:return: an automaton and a list of strings
:rtype: tuple
Note: not ov_free and end defined simultaneously
Note: end should be a Word
"""
a = fl.sigmaInitialSegment(set([str(i) for i in range(s)]), ell, True)
g = fl.RndWGen(a)
w = g.next()
if ov_free and end is not None:
l_end = len(end)
end = list(end)
we = w[-l_end:]
while we != end or not overlapFreeP(w):
w = g.next()
we = w[-l_end:]
if ov_free and end is None:
while not overlapFreeP(w):
w = g.next()
if not ov_free and end is not None:
l_end= len(end)
end = list(end)
we = w[-l_end:]
while we != end:
w = g.next()
we = w[-l_end:]
W = [w]
aut = fl.FL(W).MADFA()#toNFA()
cnt = 1
self.AutDetect = (self.Aut | self.Aut.inverse())
while cnt < N:
b = self.AutDetect.runOnNFA(aut).trim()
tr = 1
while tr <= n:
w = g.next()
if ov_free:
if not overlapFreeP(w):
continue
if end is not None:
if w[-l_end:] != end:
continue
if not b.evalWordP(w): # == False:
W.append(w)
aut = fl.FL(W).MADFA()#toNFA()
cnt += 1
break
tr += 1
if tr > n: break
return aut, W
[docs] def addToCode(self, aut, N, n=2000):
"""Returns an NFA and a list W of up to N words of length ell, such that the NFA
accepts L(aut) union W, which is an error-detecting language.
ell is computed from aut
:param NFA aut: the automaton
:param int N: the number of words to construct
:param int n: number of tries when needing a new word
:return: an automaton and a list of strings
:rtype: tuple"""
a_new = aut.dup()
W = []
u = aut.witness()
if u is None:
return a_new, W
ell = len(u)
cnt = 0
while cnt < N:
w = self.notMaxStatW(a_new, ell, n)
if w is None: break
else:
W.append(w)
a_new = a_new | fl.FL([w]).trieFA().toNFA()
cnt += 1
return a_new, W
ErrDetectProp = IPTProp # another name for IPTProp
[docs]class IATProp(IPTProp):
"""Input Altering Transducer Property
.. inheritance-diagram:: IATProp"""
def __and__(self, other):
""" Conjunction of two properties
:param IPTProp other: right hand operand
:rtype: IPTProp """
sub = isSubclass(self, other)
if sub == 1 or sub == 3:
return self
if not isinstance(other, IATProp):
if sub == 2:
return other
nt = self.Aut.dup()
n = nt.addState()
nt.addInitial(n)
nt.addFinal(n)
for s in nt.Sigma:
nt.addTransition(n, s, s, n)
name = unionOfIDs(self.ID, other.ID)
pty = IPTProp(other.Aut | nt, name)
return pty
else:
if sub == 2:
return other
name = unionOfIDs(self.ID, other.ID)
pty = IATProp(self.Aut | other.Aut, name)
return pty
[docs] def notSatisfiesW(self, aut):
"""Return a witness of non-satisfaction of the property by the automaton language
:param DFA|NFA aut: the automaton
:return: word witness pair
:rtype: tuple"""
return self.Aut.inIntersection(aut).outIntersection(aut).nonEmptyW()
[docs]class TrajProp(IATProp):
"""Class of trajectoty properties
.. inheritance-diagram:: TrajProp"""
def __init__(self, aut, Sigma):
"""Constructor
:param DFA|NFA aut: regular expression over {0,1}
:param set Sigma: the alphabet"""
super(TrajProp, self).__init__(self.trajToTransducer(aut, Sigma))
[docs] @staticmethod
def trajToTransducer(traj, Sigma):
""" Input Altering Tranducer corresponding to a Trajectory
:param NFA traj: trajectory language
:param set Sigma: alphabet
:rtype: SFT"""
t = SFT()
t.Sigma = Sigma
for s, sn in enumerate(traj.States):
no = t.stateIndex((sn, False), True)
yes = t.stateIndex((sn, True), True)
if s in traj.Final:
t.addFinal(yes)
if s in traj.Initial:
t.addInitial(no)
for b in traj.delta.get(s, {}):
for c in Sigma:
for st in traj.delta[s][b]:
fNo = t.stateIndex((traj.States[st], False), True)
fYes = t.stateIndex((traj.States[st], True), True)
if b == "0":
t.addTransition(no, c, c, fNo)
t.addTransition(yes, c, c, fYes)
if b == "1":
t.addTransition(no, Epsilon, c, fYes)
t.addTransition(yes, Epsilon, c, fYes)
return t
class FixedProp(CodeProperty):
""" Abstract class for fixed properties """
@abstractmethod
def notSatisfiesW(self, aut):
"""Test whether the language is a code.
:param DFA|NFA aut: the automaton
:return: two different factorizations of the same word
:rtype: tuple of list"""
pass
@abstractmethod
def satisfiesP(self, aut):
"""Satisfaction of the property by the automaton language
:param NFA|DFA aut: the automaton
:rtype: bool"""
pass
@abstractmethod
def maximalP(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:param DFA|NFA aut: the automaton
:rtype: bool"""
pass
@abstractmethod
def notMaximalW(self, aut, U=None):
"""Witness of non maximality
:param DFA|NFA aut: the automaton
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:return: a witness
:rtype: str"""
pass
class UDCodeProp(FixedProp):
""" Uniquely decodable Code Property
.. inheritance-diagram:: UDCodeProp"""
def __init__(self, alphabet):
super(UDCodeProp, self).__init__(('Fixed', 'UD_codes'), alphabet)
def notSatisfiesW(self, aut):
"""Test whether the language is a code.
:param DFA|NFA aut: the automaton
:return: two different factorizations of the same word
:rtype: tuple of list"""
def _findFactors(w, m):
l = []
i1 = 0
while True:
j = m.find('1', i1)
if j < 0:
break
l.append(w[i1:j + 1])
i1 = j + 1
return l
n = aut.toNFA() # .eliminateEpsilonTransitions()
for i in n.Initial:
if i in n.Final:
return [Epsilon], [Epsilon, Epsilon]
t = SFT()
t.States = copy.deepcopy(n.States)
t.setInitial(n.Initial)
t.setFinal(n.Initial)
t.setSigma(n.Sigma)
t.setOutput(['1', '0'])
for si in n.delta:
for sym in n.delta[si]:
for so in n.delta[si][sym]:
if so not in n.Final:
t.addTransition(si, sym, '0', so)
else:
t.addTransition(si, sym, '0', so)
for ss in t.Initial:
t.addTransition(si, sym, '1', ss)
t.trim()
foo = t.nonFunctionalW()
if foo == (None, None, None):
return None, None
else:
return _findFactors(foo[0], foo[1]), _findFactors(foo[0], foo[2])
def maximalP(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param DFA|NFA aut: the automaton
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:rtype: bool"""
t = infixTransducer(aut.Sigma, True)
a = aut.dup().star()
return (~(t.runOnNFA(a))).emptyP()
def satisfiesP(self, aut):
"""Satisfaction of the code property by the automaton language
:param DFA|NFA aut: the automaton
:rtype: bool"""
return self.notSatisfiesW(aut) == (None, None)
[docs]class PrefixProp(TrajProp, FixedProp):
""" Prefix Property
.. inheritance-diagram:: PrefixProp"""
def __init__(self, t):
name = ('Fixed','Prefix_codes')
IATProp.__init__(self, t, name)
[docs] def satisfiesPrefixP(self, aut):
"""Satisfaction of property by the automaton language: faster than satisfiesP
:param DFA|NFA aut: the automaton
:rtype: bool"""
if isinstance(aut, fa.DFA):
a = aut.dup()
a.trim()
for s in a.Final:
if a.delta.get(s, {}):
return False
return True
else:
return IATProp.satisfiesP(self, aut)
class SuffixProp(TrajProp, FixedProp):
""" Suffix Property
.. inheritance-diagram:: SuffixProp"""
def __init__(self, t):
name = ('Fixed','Suffix_codes')
IATProp.__init__(self, t, name)
class InfixProp(PrefixProp, SuffixProp):
""" Infix Property
.. inheritance-diagram:: InfixProp"""
def __init__(self, t):
name = ('Fixed','Infix_codes')
IATProp.__init__(self, t, name)
class OutfixProp(PrefixProp, SuffixProp):
""" Outfix Property
.. inheritance-diagram:: PrefixProp"""
def __init__(self, t):
name = ('Fixed','Outfix_codes')
IATProp.__init__(self, t, name)
class HypercodeProp(InfixProp, OutfixProp):
""" Hypercode Property
.. inheritance-diagram:: PrefixProp"""
def __init__(self, t):
name = ('Fixed','Hypercodes')
IATProp.__init__(self, t, name)
[docs]class ErrCorrectProp(ErrDetectProp):
""" Error Correcting Property
.. inheritance-diagram:: ErrCorrectProp"""
def __init__(self, t):
super(ErrCorrectProp, self).__init__(t)
self.Name = "Error Correcting Codes"
[docs] def notSatisfiesW(self, aut):
"""Satisfaction of the code property by the automaton language
:param DFA|NFA aut: the automaton
:rtype: tuple"""
return self.Aut.inverse().outIntersection(aut).nonFunctionalW()
[docs] def satisfiesP(self, aut):
"""Satisfaction of the property by the automaton language
.. seealso:: S. Konstantinidis: Transducers and the Properties of Error-Detection, Error-Correction and
Finite-Delay Decodability. Journal Of Universal Computer Science 8 (2002), 278-291.
:param DFA|NFA aut: the automaton
:rtype: bool"""
return self.notSatisfiesW(aut) == (None, None, None)
[docs] def notMaximalW(self, aut, U=None):
"""Tests if the language is maximal w.r.t. the property
:param DFA|NFA aut: the automaton
:param DFA|NFA U: Universe of permitted words (Sigma^* as default)
:rtype: bool"""
return ErrDetectProp(self.Aut.inverse().composition(self.Aut)).notMaximalW(aut, U)
def buildUDCodeProperty(alphabet):
"""Builds a UDCodeProp (from thin air ;-)
:param set alphabet: alphabet
:rtype: UDCodeProp"""
return UDCodeProp(alphabet)
buildUDCodeProp = buildUDCodeProperty
[docs]def buildTrajPropS(regex, sigma):
"""Builds a TrajProp from a string regexp
:param str regex: the regular expression
:param set sigma: alphabet
:rtype: TrajProp"""
au = reex.str2regexp(regex).toNFA()
return TrajProp(au, sigma)
[docs]def buildIATPropF(fname):
"""Builds a IATProp from a FAdo SFT file
:param str fname: file name
:rtype: IATProp"""
t = fio.readOneFromFile(fname)
return IATProp(t)
[docs]def buildIATPropS(s):
"""Builds a IATProp from a FAdo SFT string
:param str s: string containing SFT
:rtype: IATProp"""
t = fio.readOneFromString(s)
return IATProp(t)
[docs]def buildIPTPropF(fname):
"""Builds a IPTProp from a FAdo SFT file
:param str fname: file name
:rtype: IPTProp"""
t = fio.readOneFromFile(fname)
return IPTProp(t)
[docs]def buildIPTPropS(s):
"""Builds a IPTProp from a FAdo SFT string
:param str s: file name
:rtype: IPTProp"""
t = fio.readOneFromString(s)
return IPTProp(t)
[docs]def buildErrorDetectPropF(fname):
""" Builds an Error Detecting Property
:param str fname: file name
:rtype: ErrDetectProp"""
t = fio.readOneFromFile(fname)
return IPTProp(t)
[docs]def buildErrorDetectPropS(s):
""" Builds an Error Detecting Property from string
:param str s: transducer string
:rtype: ErrDetectProp"""
t = fio.readOneFromString(s)
return IPTProp(t)
[docs]def buildErrorCorrectPropF(fname):
""" Builds an Error Correcting Property
:param str fname: file name
:rtype: ErrCorrectProp"""
t = fio.readOneFromFile(fname)
return ErrCorrectProp(t)
[docs]def buildErrorCorrectPropS(s):
""" Builds an Error Correcting Property from string
:param str s: transducer string
:rtype: ErrCorrectProp"""
t = fio.readOneFromString(s)
return ErrCorrectProp(t)
[docs]def buildPrefixProperty(alphabet):
""" Builds a Prefix Code Property
:param set alphabet: alphabet
:rtype: PrefixProp"""
return PrefixProp(prefixTransducer(alphabet))
def buildSuffixProperty(alphabet):
""" Builds a Suffix Code Property
:param set alphabet: alphabet
:rtype: PrefixProp"""
return SuffixProp(suffixTransducer(alphabet))
def buildInfixProperty(alphabet):
""" Builds a Suffix Code Property
:param set alphabet: alphabet
:rtype: PrefixProp"""
return InfixProp(infixTransducer(alphabet))
def buildOutfixProperty(alphabet):
""" Builds a Outfix Code Property
:param set alphabet: alphabet
:rtype: PrefixProp"""
return OutfixProp(outfixTransducer(alphabet))
def buildHypercodeProperty(alphabet):
""" Builds a Hypercode Property
:param set alphabet: alphabet
:rtype: PrefixProp"""
return HypercodeProp(hypercodeTransducer(alphabet))
[docs]def editDistanceW(auto):
"""Compute the edit distance of a given regular language accepted by the NFA via Input-altering transducer.
.. attention::
language should have at least two words
.. seealso:: Lila Kari, Stavros Konstantinidis, Steffen Kopecki, Meng Yang. An efficient algorithm for computing
the edit distance of a regular language via input-altering transducers. arXiv:1406.1041 [cs.FL]
:param NFA auto: language recogniser
:return: The edit distance of the given regular language plus a witness pair
:rtype: tuple"""
def _normalize(tr):
tr.States = [(s1, s2, s3, s4) for (((s1, s2), s3), s4) in tr.States]
def _addTNone(tr, au, n1, s1, si, so, symb1, symb2, l):
for i1 in au.delta[si].get(symb1, []):
for i2 in au.delta[so].get(symb2, []):
new = tr.stateIndex((n1, None, i1, i2), True)
l.add(new)
if i1 in au.Final and i2 in au.Final:
tr.addFinal(new)
tr.addTransition(s1, symb1, symb2, new)
def _addT(tr, au, n1, s1, aa, si, so, symb1, symb2, l):
for i1 in au.delta[si].get(symb1, []):
for i2 in au.delta[so].get(symb2, []):
new = tr.stateIndex((n1, aa, i1, i2), True)
l.add(new)
if i1 in au.Final and i2 in au.Final:
tr.addFinal(new)
tr.addTransition(s1, symb1, symb2, new)
def _noneLoops(tr, au, l):
todo = copy.deepcopy(l)
done = set()
while todo:
s = todo.pop()
done.add(s)
(a, _, s3, s4) = tr.States[s]
for b in tr.Sigma:
for i1 in au.delta[s3].get(b, []):
for i2 in au.delta[s4].get(b, []):
new = tr.stateIndex((a, None, i1, i2), True)
if i1 in au.Final and i2 in au.Final:
tr.addFinal(new)
if new not in done:
l.add(new)
todo.add(new)
tr.addTransition(s, b, b, new)
def extendTrans(tr, au, lln, ll):
""" Extend the transducer
:param set ll: last level added states (not None)
:param set lln: last level added states (None)
:param SFT tr: the old transducer to be updated
:param NFA au: the automaton recogize the regular language
:return: last level added states lln, ll
:rtype: tuple
.. attention::
NFA au must have its state names as indexes (renameStates())"""
newll, newlln = set(), set()
for s in lln:
(m, _, s3, s4) = tr.States[s]
for a in tr.Sigma:
_addTNone(tr, au, m + 1, s, s3, s4, a, Epsilon, newlln)
_addTNone(tr, au, m + 1, s, s3, s4, Epsilon, a, newlln)
for b in tr.Sigma - {a}:
_addTNone(tr, au, m + 1, s, s3, s4, a, b, newlln)
for s in ll:
(m, a, s3, s4) = tr.States[s]
for b in tr.Sigma:
_addT(tr, au, m + 1, s, a, s3, s4, b, Epsilon, newll)
if b != a:
_addTNone(tr, au, m + 1, s, s3, s4, Epsilon, b, newlln)
for c in tr.Sigma - {b}:
_addTNone(tr, au, m + 1, s, s3, s4, c, b, newlln)
for s in newll:
(m, a, s3, s4) = tr.States[s]
for b in tr.Sigma - {a}:
_addTNone(tr, au, m, s, s3, s4, b, b, newlln)
_noneLoops(tr, au, newlln)
return newlln, newll
auto = auto.toNFA().renameStates().addEpsilonLoops()
#Todo: avoid use of inIntersectionSlow
t = createInputAlteringSIDTrans(1, auto.Sigma).inIntersectionSlow(auto).outIntersection(auto)
_normalize(t)
lvn, lv = set(), set()
for i in range(len(t.States)):
n0, a0 = t.States[i][:2]
if n0 != 0:
if a0 is None:
lvn.add(i)
else:
lv.add(i)
errn = 1
while True:
w = t.nonEmptyW()
if w != (None, None):
return errn, w
lvn, lv = extendTrans(t, auto, lvn, lv)
errn += 1
[docs]def exponentialDensityP(aut):
""" Checks if language density is exponential
Using breadth first search (BFS)
.. attention::
aut should not have Epsilon transitions
:param NFA aut: the representation of the language
:rtype: bool"""
import fractions
from collections import deque
def _listgcd(ll):
if len(ll) == 1:
return ll[0]
return fractions.gcd(ll[0], _listgcd(ll[1:]))
components = aut.trim().stronglyConnectedComponents()
for c in components:
if not len(c) == 1:
g = aut.dup()
g.deleteStates(list(set(g.indexList(g.States)) - set(c)))
marked, levelNum, levelSym = [], [], []
for _ in g.States:
marked.append(False)
levelNum.append([])
levelSym.append([])
v = g.States[0]
queue = deque()
queue.append(v)
marked[g.stateIndex(v)] = True
levelNum[g.stateIndex(v)].append(0)
while len(queue):
t = queue.popleft()
symbols = [s for s in g.delta.get(g.stateIndex(t), {})]
edges = [g.delta[g.stateIndex(t)][k] for k in symbols]
for s in symbols:
if s not in levelSym[levelNum[g.stateIndex(t)][0]]:
levelSym[levelNum[g.stateIndex(t)][0]].append(s)
for e in edges:
for o in e:
levelNum[o].append(levelNum[g.stateIndex(t)][0] + 1)
if not marked[o]:
marked[o] = True
queue.append(g.States[o])
if [l for l in levelSym if len(l) > 1]:
return True
lengths = []
for s in levelNum:
first = s[0]
for n in [m for m in s if m - first]:
lengths.append(n - first)
d = _listgcd(lengths)
if d == 1:
return True
pattern = ""
for i in range(0, d):
pattern = pattern + levelSym[i][0]
for j in range(d, max(lengths)):
if not levelSym[j][0] == pattern[j % d]:
return True
return False
def long2base(n, q):
""" Maps n to a list of digits corresponding to the base q representation of n in reverse order
:param int n: a positive integer
:param int q: base to represent n
:return: list of q-ary 'digits', that is, elements of {0,1,..,q-1}
:rtype: list"""
lt = []
while n > 0:
lt.append(n % q)
n /= q
return lt
def list2string(lt, dy):
"""
:param list lt: list of nonnegative integers from some set {0,1,...,q-1}
:param dict dy: mapping from {0,1,...,q-1} to some alphabet symbols
:return: string of symbols corresponding to the integers in lt
:rtype: str"""
return "".join([dy[i] for i in lt])
def notUniversalStatW(a, l, maxIter=20000):
""" Tests statistically whether the NFA a is l-non-universal, by evaluating a on <= maxIter randomly chosen words of length l
:type a: NFA
:param int l: nonnegative integer
:type maxIter: int
:return: (w,i) where w is the word found at i-th try; or (None, i) after i tries
:rtype: tuple"""
if l == 0: # first handle the case of the empty word
if a.evalWordP(Epsilon):
return None, 1
else:
return Epsilon, 1
lt = [s for s in a.Sigma]
# dictionary dy is used to refer to each alphabet symbol in lt using a numeric index
dy = {i: lt[i] for i in range(0, len(lt))}
q = len(lt)
numWords = q ** l
tmp = set() # will remember in tmp the distinct words generated so far
random.seed()
for j in range(0, maxIter):
# next pick one word out of the possible numWords of length l; specifically pick
# the i-th one, where i is randomly chosen. For this, choose a random int n whose
# base q representation is of the form '1d_1...d_l', where the l d's are digits
# in {0,1,...,q-1}, so the desired number i is the one represented as 'd_1...d_l'
n = random.randint(numWords, 2 * numWords - 1)
w = list2string(long2base(n, q), dy)[:l]
if not a.evalWordP(w):
return w, j + 1
tmp.add(w) # Note: the current random word could be equal to a past one !!
if len(tmp) == numWords:
return None, numWords
return None, maxIter
def symmAndRefl(t, ipt=False):
""" Return the transducer t | t.inverse, if ipt is True;
return the transducer t | t.inverse | id, otherwise
:type t: SFT
:type ipt: bool
:rtype: SFT"""
t1 = t | t.inverse()
if ipt is True:
return t1
t2 = SFT()
s0 = t2.addState()
t2.addInitial(s0)
t2.addFinal(s0)
for sym in t.Sigma:
t2.addTransition(s0, sym, sym, s0)
return t1 | t2
def constructCode(n, l, p, ipt=False, seed=None):
""" Returns up to n words of length l satisfying the property p, the first one being seed.
If ipt is True, the property is assumed to be input-preserving transducer type
:type p: IATProp|IPTProp
:type l: int
:type n: int
:type seed: str
:type ipt: bool
:rtype: list"""
if n == 0:
return []
if l == 0:
return [Epsilon]
t = symmAndRefl(p.Aut, ipt) # make a version of p.Aut that is symmetric and reflexive
if seed is None or len(seed) != l:
a0 = list(t.Sigma)[0]
seed = "".join([a0 for _ in range(l)])
lt = [seed]
cnt, more = 1, True
while more and cnt < n:
a = fl.FL(lt).trieFA().toNFA()
b = t.runOnNFA(a)
(w, i) = notUniversalStatW(b, l)
if w is None:
more = False
else:
cnt += 1
lt.append(w)
return lt