PROLOG特定の有限状態オートマトン

Question

次の問題の答えが見つかりません。オートマトンは "A：5739"のような文字列を受け入れます。または "C :: 399 \ 4342）"、これらは私にファイルシステムのパスを思い出させますが、私はそれについてはわかりません。

問題のテキスト：

はPrologで書かれた以下の有限状態オートマトンを考えてみましょう。 認識されるようですか？

は、その引数が文字または数字であるとき真である述語

alphanumeric/1 

を持つものとします。

オートマトン：

accept([I | Is], S) :- delta(S, I, N), accept(Is, N). 
accept([], Q) :- final(Q). 

initial(start). 
final(type). 

delta(start, 'A', dev). 
delta(start, 'B', dev). 
delta(start, 'C', dev). 
... 
delta(start, 'Z', dev). 
delta(dev, ':', n1). 

delta(n1, '\', dev). 
delta(n1, L, name) :- alphanumeric(L). 
delta(name, L, name) :- alphanumeric(L). 
delta(name, '\', name). 
delta(name, '.', type). 
delta(name, L, type) :- alphanumeric(L). 

Answer 1

まあ最初の2つの句はNDFAが常に実行される方法を単純です：私たちは得ることが、リスト内の次の文字を検索し、delta/3述語を介してこれを通過するたびに、シーケンスの最後に到達するまで新しい状態を返します。その後、状態が受諾状態であるかどうかを確認できます。

次に、startが初期状態であり、typeが唯一の受け入れ状態であることがわかります。

残りのプログラムでは、delta/3の遷移が説明されています。

digraph finite_state_machine { 
    rankdir=LR; 
    size="8,5" 
    node [shape = doublecircle]; type; 
    node [shape = circle] start, dev, n1; 
    node [shape = circle, label="name"] nam; 

    start -> dev [ label = "[A-Z]" ]; 
    dev -> n1 [ label = ":" ]; 
    n1 -> dev [ label = "\\" ]; 
    n1 -> nam [ label = "[A-Za-z0-9]" ]; 
    nam -> nam [ label = "[A-Za-z0-9\\]" ]; 
    nam -> type [ label = "[A-Za-z0-9.]" ]; 
} 

これは、次の画像生成：私たちはGraphVizを使用して、インスタンスのために、これをvizualizeすることができ、この図に基づいて

、我々はそれが言語（正規表現表記）を受け入れることを確認します：

[A-Z]:(\:)*[A-Za-z0-9][A-Za-z0-9\]*[A-Za-z0-9.] 

したがって、文字AZで始まり、コロン（:）に続いて0個以上のバックスラッシュコロン（:\）が続き、英数字の後に単語グループ[A-Za-z0-9\.]に続けてゼロ以上の文字が続き、その後に少なくとも1つの英数字が続きます。

したがって、たとえば：

X:\:0Azz0qdqd012QcCQCA 
D:\:QA 
B:\:\:QT 
C:QWR. 
C:\:a\q\b\QWR. 
C:tempdir\bla\qux. 
C:tempdir\bla\. 
C:. 

それが唯一の最後の文字としてドットを含めることができます。さらに、バックスラッシュを最後の文字にすることはできません。これは基本的なファイルパス言語ですが、いくつかの再構成があります。