📄 ftrellis.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1996 ACM Finals, Problem F - Nondeterministic Trellis Automata</TITLE>
<!SGML "ISO 8879:1986">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H1>
1996 ACM Scholastic Programming Contest Finals</H1></CENTER>
<CENTER>
<H4>
sponsored by Microsoft</H4></CENTER>
<CENTER>
<H1>
Problem F</H1></CENTER>
<CENTER>
<H2>
Nondeterministic Trellis Automata</H2></CENTER>
<CENTER>
<H3>
Input file: trellis.in</H3></CENTER>
A <I>nondeterministic trellis automaton</I> (NTA) is a kind of parallel
machine composed of identical finite-state processors arranged in an infinite
triangular trellis. The top, or apex, of the triangle is a single processor.
The next row has two processors and each successive row of an NTA has one
more processor than the row above it. Each processor in an NTA is connected
to two children in the row below it. Computation in an NTA occurs bottom
up; the state of each processor in a row is based on the state of the processor's
children and a transition table. The input to an NTA is the initial configuration
of one row of processors. The input is specified by a string that gives
the initial state of each processor in a row so that an <I>n</I>-character
string specifies the initial configuration for a row of <I>n</I> processors.
Computation proceeds up the NTA to the apex by nondeterministically calculating
the state of each processor in a row based on the transition table and
the state of the processor's children in the row below.
<P>
<P>Some states are identified as accepting states. Some transitions are
computed nondeterministically. An input is <I>accepted</I> if some computation
puts the apex processor into an accepting state. An input is <I>rejected</I>
if no computation puts the apex processor into an accepting state. For
example, the table below shows transitions for a 3-state NTA. States are
labeled by characters "a", "b", and "c"; the only accepting state is "c".
<P>
<BLOCKQUOTE><IMG SRC="trellis1.gif" ></BLOCKQUOTE>
The diagram below shows two computations for the input "bba". The computation
on the left rejects the input since the state of the apex is "a"; but the
computation on the right accepts the input since the state of the apex
is "c". Since some computation results in an accepting state for the apex,
the input "bba" is accepted by the NTA. The input "bbb" would be rejected
by this NTA since the only computation results in the state "a" for the
apex.
<P>
<CENTER><IMG SRC="trellis2.gif" ></CENTER>
<H3>
<HR>Input</H3>
The states (and inputs) of an NTA are consecutive lowercase letters. Thus
the states for a 5-state NTA are "a", "b", "c", "d", and "e". Accepting
states are grouped at the end of the letters so that if a 5-state NTA has
two accepting states, the accepting states are "d" and "e".
<P>
<P>The input for your program is a sequence of NTA descriptions and initial
configurations. An NTA description is given by the number of states <I>n</I>
followed by the number of accepting states on one line separated by whitespace.
The <I>n</I> × <I>n</I> transition table follows in row-major order; each
transition string is given on a separate line. Each NTA description is
followed by a sequence of initial configurations, one per line. A line
of "#" terminates the sequence of initial configurations for that NTA.
An NTA description in which the number of states is zero terminates the
input for your program.
<P>NTAs will have at most 15 states, initial configuration will be at most
15 characters.
<H3>
<HR>Output</H3>
For each NTA description, print the number of the NTA (NTA 1, NTA 2, etc.
). For each initial configuration of an NTA print the word "accept" or
"reject" followed by a copy of the initial configuration.
<H3>
<HR>Sample Input</H3>
<PRE>3 1
a
a
c
ca
a
b
c
b
a
bba
aaaaa
abab
babbba
a
baaab
abbbaba
baba
bcbab
#
3 2
ab
a
c
a
ab
b
c
b
ab
abc
cbc
#
0 0</PRE>
<H3>
<HR>Output for the Sample Input</H3>
<PRE>NTA 1
accept bba
reject abab
accept babbba
reject a
reject aaaaa
accept baaab
accept abbbaba
accept baba
reject bcbab
NTA 2
reject abc
accept cbc</PRE>
<HR NOSHADE>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -