计数语言

定义

计数语言的集合是指可以通过计数自动机生成的语言集合，计数自动机是一种确定性有限自动机（DFA）（参见正则语言），具有有限数量的无限计数器。这些计数器可以在状态转换期间增加或减少，它们的状态可用于确定转换。

语言类层次结构中的位置

如果计数器未使用，则计数自动机等效于 DFA，因此正则语言是计数语言的子集。还有一些上下文无关语言是计数语言（例如 {aⁿbⁿ | n ≥ 0}），上下文无关语言不是计数语言（乔姆斯基这样说但从不给出示例），以及上下文相关（但不是上下文无关）语言是计数语言（例如 {aⁿb^maⁿb^mccc | n,m ≥ 0}）。线性有界自动机（参见上下文相关语言）可以通过假设计数器不能达到大于输入字符串长度的值来模拟计数自动机，因此可以将计数器信息存储在与输入字符串大小线性相关的空间量中。CA 的其余部分本质上是一个 DFA，LBA 也可以在线性空间中模拟 DFA。线性空间加上线性空间仍然是线性的，因此计数语言是上下文相关语言的子集，与上下文无关语言相交但不嵌套。

示例

下面的代码是 Perl 中的示例 CA 模拟器。给定机器的描述和输入字符串，它模拟机器处理输入字符串，并显示机器是否接受。

语法是：progname.pl CAFile inputFile，其中 CAFile 是包含 CA 指令的文本文件，inputFile 是包含输入字符串的文本文件。一些示例输入，包括用于识别 $\{a^{n}b^{m}a^{n}b^{m}ccc|n,m\geq 0\}$ 的机器的 CA 指令集，可以在示例 CA 输入下找到。

#!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;
}

上一步 | 下一步