What people are saying - Write a review
We haven't found any reviews in the usual places.
Mathematical preliminaries l
The syntactic monoid
6 other sections not shown
1-productions accessible automaton aia2 alphabet and let anbn aperiodic aperiodic monoids automata automaton recognizing block of a's Boolean algebra C L(T Cayley table certainly Chomsky Normal Form computation beginning computation fails congruence consider contains context-free grammar context-free languages contradiction Cv(A deduce defined definition denote diagram equivalence example Exercise exists F-variety fact finite alphabet finite monoid finite set finite state automaton follows free monoid given Hence identity element induction initial integer language recognized left factor leftmost derivation length memory stack minimal automaton morphism morphism ip move right non-empty notation Notice p-classes palindromes Proof Pumping Lemma pushdown automaton q in Q rational language recognizable regular grammar Section semigroup sequence simulated submonoid subroutine suppose Syn(L syntactic monoid T-computation terminal transformation monoid trivial productions Turing machine typical successful computation word write