計數語言

定義

計數語言的集合是指可以透過計數自動機生成的語言集合，計數自動機是一種確定性有限自動機（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;
}

上一步 | 下一步