「言語のDFA」の定義

Question

今学期の理論計算を始めたばかりで、「言語のためのDFA」というフレーズで少し混乱しました。バイナリ文字列LのコレクションのDFAを作成するように要求されている場合は、L（M）= Lまたは$ L（M）\ supset L $のDFA Mを見つけることを意味しますか？

Answer 1

ほとんどのコンパイラ/理論コースは、決定論的有限オートマトンと公式言語の教授定義を取り巻くさまざまなスタイルを持つ傾向がありますが、私はこの記述を可能な限り不可分なものにしようとします。

「言語用のDFA」とは、言い換えれば、wordをすべて受け取り、すべての言語でwordを拒否するDFAを意味します。 私がDFAを教えたやり方は、暗黙のエラー状態の必要性を排除する最終状態/受け入れ状態と通常の状態を持つことです。 これは、入力の末尾にある状態がacceptingである場合、DFAは単語を受け入れ、状態がacceptingでない場合、その単語を拒否します。

例：

のは、偶数個の1が含まれている言語としてLを定義してみましょう。これらはバイナリ文字列であり、シンボルは0と1だけです。 00,110, 111 ,1111などはこの言語の単語の例です。空の文字列はこの言語であることに注意してください。

DFAには2つの州があります。開始状態は、even 1sとも呼ばれますが、0が偶数であるため受け入れ状態です。他の状態はodd 1sですが、これは受け入れられません。

遷移については、even 1sが1を受信すると、odd 1sに遷移します。 odd 1sが1を受信すると、even 1sに遷移します。 ここで0の数は関係ありません。したがって、いずれの状態でも0の数はそれ自体に移行します。二重の矢印の

謝罪、このwebsiteは素晴らしいですが、私はeven 1sとodd 1s

間の遷移を分離する方法を見つけ出すことができませんでした

Answer 2

質問を正確に書いてください。ここでDFAとは、特定の言語のマシンをサブセットやスーパーセットでなく構築する必要があることを意味します。