Counting Languages

Definition

The set of counting languages is the set of languages that can be generated by a counter automaton, a deterministic finite automaton (DFA) (see Regular Languages) with a finite number of infinite counters. These counters can be incremented or decremented during state transitions, and their statuses can be used to determine transitions.

Position in the Hierarchy of Language Classes

If the counters are unused, a counter automaton is equivalent to a DFA, so the regular languages are a subset of the counting languages. There are also context free languages that are counting languages (such as {aⁿbⁿ | n ≥ 0}), context-free languages that are not counting languages (Chomsky says so but never gives an example), and context-sensitive (but not context-free) languages that are counting languages (such as {aⁿb^maⁿb^mccc | n,m ≥ 0}). A linear bounded automaton (see Context Sensitive Languages) can emulate a counter automaton by assuming that the counters cannot reach values greater than the length of the input string, and thus can store the counter information in an amount of space linearly based on the size of the input string. The rest of the CA is essentially a DFA, which LBAs can also emulate in linear space. Linear space plus linear space is still linear, so the counting languages are a subset of the context-sensitive languages, and intersect but are not nested with the context-free languages.

Example

The code below is a sample CA emulator in Perl. Given the description of a machine and an input string, it simulates the machine processing the input string, and shows whether the machine accepts or not.

The syntax is: progname.pl CAFile inputFile, where CAFile is a text file containing the CA instructions, and inputFile is a text file containing the input string. Some sample inputs, including a set of CA instructions for a machine to recognize $\{a^{n}b^{m}a^{n}b^{m}ccc|n,m\geq 0\}$ , can be found under sample CA inputs.

#!usr/bin/perl
use Text::ParseWords;
use strict;
use warnings;

# Grabs the filenames for the machine and the word to be run on it.
my $caFile = $ARGV[0];
my $input = $ARGV[1];

# Uses subroutines to parse and verify the data in the input files.
# The machine data is stored in the $machine structure as the keys rules, accepts, alphabet, and startState.
my $machine = readCA($caFile);
# Rules, counters, and accepts are extracted from the $machine structure for ease of access.
my @rules = @{$machine->{rules}};
my %counters = %{$machine->{counters}};
my %accepts = %{$machine->{accepts}};
# The $state variable holds the current state of the machine, and is initialized to the start state from the machine file.
my $state = $machine->{startState};
# This reads the input file and parses it into an array of strings, with each element being one input symbol
# It checks to make sure the elements are all in the machine's alphabet.
my @string = readInput($input, $machine->{alphabet});
my $changed = 0;

# For each symbol in the input word, the next state is calculated.
for my $s (0..$#string)
{
   # The input word is printed, with the next symbol highlighted.
    print "@string[0..$s-1] <".$string[$s]."> @string[$s+1..$#string] |";
   # The current state of the counters is printed.
    while( my ($k, $v) = each %counters ) {
        print " $k: $v";
    }
    print "\n";
   # A new state is calculated by checking conditions against the list of rules
    RULESLOOP: for my $ruleRef (@rules)
    {
       # Checks the current state and input against the rule
        if ($ruleRef->[0] eq $state && $ruleRef->[1] eq $string[$s])
        {
           # Checks the counter conditions
            for my $cNum (4..$ruleRef->[3])
            {
               # If the conditions don't match, this rule doesn't work.
                unless (eval $ruleRef->[$cNum]) { next RULESLOOP; }
            }
           # Set the new state.
            my $newstate = $ruleRef->[2];
           # The state transition is printed.
            print "State: ".$state." -> ".$newstate."\n\n";

            for my $cNum ($ruleRef->[3]+1..$#$ruleRef)
            {
               # Update the counters
                eval $ruleRef->[$cNum];
            }
           # The state changes to the new state.
            $state = $newstate;
            $changed = 1;
           # Since we've used a rule, we can stop looking and get new input
            last RULESLOOP;
        }
    }
   # But if a rule wasn't used, then there were no valid transitions and the machine stops
    last unless $changed;
    $changed = 0;
}
# When the input is exhausted, the machine is in its final state.
print "Final state is ".$state."\n";
# If that state is in the accept states list, the machine accepts the input.
if (exists($accepts{$state})) { print "The machine accepts the string.\n"; }
# If not, the machine rejects.
else { print "The machine does not accept the string.\n" }

###################################################

sub readCA
# This subroutine reads the machine data from the specified file into variables (mostly hashes).
{
    my (%states, %counters, %accepts, %alphabet, @rules);
    open(INFILE, shift) or die "Can't open machine file: $!";
    
# This block reads the list of states from the machine file.
   # Discards the section header,
    <INFILE>;
    my $line = <INFILE>;
    chomp($line);
    my @words = parse_line('\s+', 0, $line);
    for (@words)
    {
       # records the state names for checking the rules,
        $states{$_} = 0;
    }

# This block reads the number of counters from the machine file.
   # Discards the section header,
    <INFILE>;
    $line = <INFILE>;
    chomp($line);
    @words = parse_line('\s+', 0, $line);
    for (@words)
    {
       # then initializes the counters.
        $counters{$_} = 0;
    }
    
# This block reads the start state from the machine file.
   # Discards the header,
    <INFILE>;
    my $startState = <INFILE>;
   # takes the whole line as the start state,
    chomp($startState);
   # and makes sure that the start state is defined in the list of states.
    exists($states{$startState}) or die "The start state $startState isn't a state!";
    
# This block reads the list of accepting states from the machine file.
   # Discards the header,
    <INFILE>;
    $line = <INFILE>;
    chomp($line);
   # breaks up the line into state names,
    @words = parse_line('\s+', 0, $line);
    for (@words)
    {
   # checks to make sure that the accept states are defined states,
        exists($states{$_}) or die "$_ isn't a state!";
   # and defines those names in a new hash.  The use of a hash makes it easier to determine later if a specific state name accepts or not.
        $accepts{$_} = 1;
    }
    
# This block reads the list of symbols in the alphabet from the machine file.
   # Discards the header,
    <INFILE>;
    $line = <INFILE>;
    chomp($line);
   # breaks up the line into alphabet symbols (note that the symbols can be of arbitrary length),
    @words = parse_line('\s+', 0, $line);
    for (@words)
    {
       # This records which symbols are in the alphabet for checking the rules.
        $alphabet{$_} = 0;
    }
    
# This block reads the state transition rules from the machine file.
   # Discards the header,
    <INFILE>;
   # This variable synchronizes the position of each rule in the rules array.
    my $rulesCounter=0;
    while(<INFILE>)
    {
   # breaks each rule into start state, input symbol, and end state,
        chomp;
        @words = parse_line('\s+', 0, $_);
   # checks that all three pieces are defined in the state and alphabet hashes,
        exists($alphabet{$words[1]}) or die "$words[1] isn't defined in the alphabet!";
        exists($states{$words[0]}) or die "$words[0] isn't a defined state!";
        exists($states{$words[2]}) or die "$words[2] isn't a defined state!";
   # then creates an array of each rule.
        splice(@words,3,0,$#words);
        for (0..$#words)
        {
           # If there is a '->', then what follows is counter updates, not counter checks.
            if ($words[$_] =~ /->/)
            {
               # Remove that piece from the array
                splice(@words,$_,1);
               # And note it's position in slot 3.
                $words[3] = $_-1;
                last;
            }
        }
       # The first 4 slots can be copied verbatim (remember that slot 3 is location of the last counter check command
        for (0..3)
        {
            $rules[$rulesCounter][$_] = $words[$_];
        }
       # The counter checks and updates must be turned into commands.
        for (4..$#words)
        {
            $words[$_] =~ s/([a-z]*)/\$counters{$1}/i;
            $rules[$rulesCounter][$_] = $words[$_];
        }
       # The synchronization variable has to be updated.
        $rulesCounter++;
    }

# Reading complete, the subroutine closes the file and returns the name of the start state.
    close INFILE;
    my $machine = 
    {
        rules      => \@rules,
        accepts    => \%accepts,
        alphabet   => \%alphabet,
        counters   => \%counters,
        startState => $startState
    };
    return $machine;
}

sub readInput
# This subroutine reads the input string from the specified file into an array of symbols.
{
    open(INFILE, shift) or die "Can't open input file: $!";
    my $alphaRef = shift;
   # The first line of the file is read as the input, with symbols delimited by spaces.
    my $line = <INFILE>."";
    chomp($line);
    my @string = parse_line('\s+', 0, $line);
   # This makes sure every symbol in the input string was defined in the machine's alphabet.
    for (@string)
    { exists($alphaRef->{$_}) or die "$_ in $input isn't in this machine's alphabet!"; }
    close INFILE;
    return @string;
}

Previous | Next

Computability and Complexity/Formal Languages/Other Language Classes/Counting Languages

Contents

Counting Languages

Definition

Position in the Hierarchy of Language Classes

Example