Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from itertools import chain
- EPSILON = object()
- class GNFA:
- """
- tests:
- >>> a = GNFA('a', ['ab1'], set('b'))
- >>> a.pre('a')
- set([])
- >>> a.post('a')
- set(['b'])
- >>> a.pre('b')
- set(['a'])
- >>> a.post('b')
- set([])
- """
- def __init__(self, startState, transitions, finalStates):
- ## infer state set from transitions
- self.states = set()
- self.states.update(q for q, r, lab in transitions)
- self.states.update(r for q, r, lab in transitions)
- assert startState in self.states
- self.startState = startState
- self._labels = dict(((q, r), lab) for q, r, lab in transitions)
- self.transitions = Index(transitions, 'start end label'.split())
- assert finalStates <= self.states
- self.finalStates = finalStates
- def __str__(self):
- return ("startState => %(startState)s\n"
- "transitions => %(transitions)s\n"
- "finalStates => %(finalStates)s" %
- self.__dict__ )
- def re(self):
- """
- test:
- >>> a = GNFA('a', ['ab1'], set('b'))
- >>> a.re()
- '1'
- >>> import re
- >>> a2 = GNFA('a', ['ab1', 'ba1', 'ac0', 'ca0', 'bd0', 'db0', 'cd1', 'dc1'], set('b'))
- >>> eo = re.compile(a2.re() + '$')
- >>> def binary(n):
- ... if n == 0: return '0'
- ... digits = []
- ... while n:
- ... if n % 2: digits.append('1')
- ... else: digits.append('0')
- ... n >>= 1
- ... return ''.join(reversed(digits))
- >>> binary(0)
- '0'
- >>> binary(1)
- '1'
- >>> binary(2)
- '10'
- >>> binary(3)
- '11'
- >>> binary(4)
- '100'
- >>> binary(5)
- '101'
- >>> binary(6)
- '110'
- >>> binary(7)
- '111'
- >>> def eo_p(s): return s.count('1') % 2 == 1 and s.count('0') % 2 == 0
- ...
- >>> for n in range(10000):
- ... s = binary(n)
- ... if eo_p(s) != bool(eo.match(s)):
- ... print n
- ... break
- ...
- """
- normalized = self.normalized()
- ## rip states in self from normalized
- for q in self.states:
- normalized.irip(q)
- ## return single remaining label in normlized
- res = list(normalized._labels.values())
- assert len(res) == 1
- return res[0]
- def normalized(self):
- startState = object() # construct a new start and end states
- finalState = object()
- ## add transitions from new start state and to new end state
- transitions = set(self.transitions)
- transitions.add( (startState, self.startState, EPSILON) )
- transitions.update((f, finalState, EPSILON) for f in self.finalStates)
- return GNFA(startState, transitions, set([finalState]))
- def irip(self, q):
- """
- tests:
- >>> a = GNFA('a', ['ab0', 'bc0'], set(['c']))
- >>> a.irip('b')
- >>> print a
- startState => a
- transitions => set([('a', 'c', '00')])
- finalStates => set(['c'])
- >>> a._labels
- {('a', 'c'): '00'}
- """
- pre = self.pre(q)
- post = self.post(q)
- selfLoop = self._labels.get( (q,q), EPSILON )
- ## add new new transitions corresponding to paths going through q
- for p in pre:
- for r in post:
- lab = reConcat(self._labels[p,q],
- reStar(selfLoop),
- self._labels[q,r] )
- self.addTransition(p, r, lab)
- self.removeState(q)
- def addTransition(self, q, r, lab):
- """
- test:
- >>> a = GNFA('a', ['ab1'], set('b'))
- >>> a.addTransition('a', 'b', 'the world is ending')
- '(1|the world is ending)'
- >>> print a
- startState => a
- transitions => set([('a', 'b', '(1|the world is ending)')])
- finalStates => set(['b'])
- >>> a._labels
- {('a', 'b'): '(1|the world is ending)'}
- """
- if (q, r) in self._labels:
- oldLab = self._labels[q,r]
- newLab = reUnion(oldLab, lab) # union labels
- self._labels[q,r] = newLab # update self._labels with new label
- self.transitions.remove(q, r, oldLab) # update self.transitions with new transition
- self.transitions.add(q, r, newLab)
- return newLab
- else:
- self._labels[q,r] = lab
- self.transitions.add(q, r, lab)
- return lab
- def removeState(self, q):
- """
- tests:
- >>> a = GNFA('a', ['ab1'], set('b'))
- >>> a.removeState('b')
- >>> print a
- startState => a
- transitions => set([])
- finalStates => set([])
- >>> a._labels
- {}
- """
- if q == self.startState:
- raise ValueError('Cannot remove the start state.')
- pre = self.pre(q)
- for p in pre:
- lab = self._labels[p,q]
- self.transitions.remove(p, q, lab)
- del self._labels[p,q]
- post = self.post(q)
- for r in post:
- lab = self._labels[q,r]
- self.transitions.remove(q, r, lab)
- del self._labels[q,r]
- if (q,q) in self._labels:
- lab = self._labels[q,q]
- self.transitions.remove(q, q, lab)
- del self._labels[q,q]
- self.finalStates.discard(q) # discard succeeds even if q does not exist
- def pre(self, q):
- """Returns a set of predecessors.
- Result does not include argument.
- """
- return self.transitions.project1(
- self.transitions.select(1, q),
- 'start' ) - set([q])
- def post(self, q):
- """Returns a set of successors.
- Result does not include argument.
- """
- return self.transitions.project1(
- self.transitions.select(0, q),
- 'end' ) - set([q])
- class Index:
- """
- tests:
- >>> i = Index(['abc', 'adc', 'bbb'])
- >>> i.select(0, 'crazy')
- set([])
- >>> i.select(1, 'crazy')
- set([])
- >>> i.select(2, 'crazy')
- set([])
- >>> i.select(0, 'a')
- set([('a', 'b', 'c'), ('a', 'd', 'c')])
- >>> i.select(0, 'b')
- set([('b', 'b', 'b')])
- >>> i.select(1, 'b')
- set([('b', 'b', 'b'), ('a', 'b', 'c')])
- >>> i.select(2, 'c')
- set([('a', 'b', 'c'), ('a', 'd', 'c')])
- >>> i.removeTuple('bbb')
- >>> print i
- set([('a', 'b', 'c'), ('a', 'd', 'c')])
- """
- def __init__(self, tuples, columnNames=None):
- ## set self.columnNames and determine arity
- if columnNames is None:
- arity, tuples = inferArity(tuples)
- self.columnNames = columnNames = range(arity)
- else:
- self.columnNames = columnNames
- arity = len(columnNames)
- ## for determining column number
- self._columnName2columnNumber = dict((name, n) for n, name in enumerate(columnNames))
- self._tables = [{} for x in range(arity)] # initialize indeces
- self.update(tuples) # populate indeces
- def getArity(self): return len(self.columnNames)
- arity = property(getArity)
- def __iter__(self):
- return chain(*self._tables[0].values())
- def __str__(self):
- return str(set(iter(self)))
- def select(self, col, val):
- return self._tables[self.columnNumber(col)].get(val, set())
- def project(self, tuples, *cols):
- cols = map(self.columnNumber, cols)
- return set(tuple(tup[i] for i in cols) for tup in tuples)
- def project1(self, tuples, col):
- col = self.columnNumber(col)
- return set(tup[col] for tup in tuples)
- def columnNumber(self, col):
- try:
- return self._columnName2columnNumber[col]
- except KeyError as ex:
- if isinstance(col, int):
- return col
- raise
- def update(self, tuples):
- for tup in tuples:
- self.addTuple(tup)
- def add(self, *tup):
- self.assertArity(tup)
- ## update all tables
- for val, tab in zip(tup, self._tables):
- tab.setdefault(val, set()).add(tup)
- def addTuple(self, tup):
- self.add(*tup)
- def remove(self, *tup):
- """Removes the tuple.
- Tuple must exist.
- """
- self.assertArity(tup)
- ## remove from all tables
- for val, tab in zip(tup, self._tables):
- tab[val].remove(tup)
- def removeTuple(self, tup):
- self.remove(*tup)
- def assertArity(self, tup):
- if len(tup) != self.arity:
- raise ValueError("%d arguments given to an Index with arity %d." %
- (len(tup), self.arity) )
- def reConcat(*res):
- """
- tests:
- >>> reConcat('a', 'b')
- 'ab'
- >>> reConcat('a', EPSILON)
- 'a'
- """
- return ''.join(re for re in res if re is not EPSILON)
- def reUnion(*res):
- """
- tests:
- >>> reUnion('a', 'b')
- '(a|b)'
- >>> reUnion('a', EPSILON)
- '(a)'
- """
- return '(' + '|'.join(re for re in res if re is not EPSILON) + ')'
- def reStar(re):
- """
- tests:
- >>> reStar('a')
- '(a)*'
- >>> reStar(EPSILON) is EPSILON
- True
- """
- if re is EPSILON:
- return EPSILON
- else:
- return '(%s)*' % re
- def inferArity(tuples):
- tup, rest = first(tuples)
- return len(tup), chain((tup,), rest)
- def first(seq):
- """Returns the first element, and an iterator with the remaining elements.
- If there is no first element, throw StopIteration.
- """
- it = iter(seq)
- return it.next(), it
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement