プッシュダウンオートマトンと無限要素を含む文脈自由で規則的な言語

Question

私は理論クラスのためのHW割り当てを行っていて、どこから始めるべきかわからないという問題に直面しました。プッシュダウンオートマトンのセクションをカバーしています。

"L1を文脈自由言語とし、L2を規則正しくする。L1とL2に無限の共通要素があるかどうかを判断するアルゴリズムが存在することを示す。

これを解決する方法についてはわかりません。アイデアをつかむことができません。私は、規則的な言語はあいまいさを許さず、それがこの問題のために考慮する必要があるかどうか疑問に思っています。また、それが "プッシュダウンオートマトン"セクションにあると、私はそれがnpdaまたはpdaを作成する必要があるかもしれないと仮定しています。誰でも少なくとも私を正しい方向に向けることができますか？ HWの解決を求めるのではなく、HWの助けを求めること！ L1用PDA A1およびL2のためのDFA A2考える

Answer 1

1. 、次の2つのDFAの間と同じように、デカルト製品機械構造を使用してL1とL2の交点を認識するA3を構築します。正式な構築はちょっと面倒ですが、基本的に古いものの組み合わせを追跡し、必要に応じて遷移/スタックの変更を追加する新しい状態があります。

2. A3から標準構造を使用してCFG G3を構築します。繰り返しますが、証明は面倒ですし、面倒な文法で終わることもありますが、これも実行できます。

3. G3から無駄な変数、空とユニットプロダクションを削除します。あなたがChomsky Normal Form（CNF）に慣れていれば、これは基本的に同様のプロセスです。

4. 非終端記号の依存グラフを作成します。依存関係グラフにループがある場合、G3の言語は無限になります。

5. G3は、L1とL2の間に共通する単語の文法であるため、L1とL2の単語が無限に多くなると、無限に多くの単語が生成されます。