Computability and Complexity/Formal Languages/Other Language Classes/sample CA inputs

Sample CA inputs

These examples are for use with the perl CA emulator provided at the bottom of Counting Languages. That page also contains a description of what a CA is and how it works.

This machine accepts strings of the form $\{a^{n}b^{m}a^{n}b^{m}ccc|n,m\geq 0\}$.

:States:
q1a q1b q2a q2b q3 q4 q5 q6 q7
:Counters:
m n
:Start State:
q1a
:Accept States:
q7
:alphabet:
a b c
:rules:
q1a c q5
q1a a q1b -> m++
q1b a q1a -> m++
q1a b q2b -> n++
q1b b q2b -> n++
q2a b q2b -> n++
q2b b q2a -> n++
q2a c q5 m==0
q2a a q3 m>0 -> m--
q2b a q3 m>0 -> m--
q3 a q3 m>0 -> m--
q3 b q4 m==0 n>0 -> n--
q4 b q4 n>0 -> n--
q4 c q5 n==0
q5 c q6
q6 c q7

Some sample inputs:
These accept:

a b b b a b b b c c c

c c c

a a a a c c c

These reject:

a a b b a b b c c c

a a b a a b c c

a a a c c c

back