プロが教えるわが家の防犯対策術！

[大学数学 形式言語]回文を受理するオートマトンの設計

解決済

  • 質問者：ktnabe
  • 質問日時：
  • 回答数：2件

入力として0,1上の文字列を受理するNFA,(またはλ-NFA)を設計したいのですが、どう考えればいいのかわかりません。よろしくお願いします。

質問者からの補足コメント

  • ご回答ありがとうございます。
    ω-> 0ω0 または 1ω1 または 0 または 1 または λ
    でしょうか？？
    確かに、授業で右線形文法と正則言語は同値であるということをやった気がします！
    ただ、この文法を右線形に書き換える方法が思いつかなかったです。

    No.1の回答に寄せられた補足コメントです。 補足日時：2024/02/09 17:54
    通報する
通報する

この質問への回答は締め切られました。

質問の本文を隠す

A 回答 (2件)

No.1ベストアンサー

  • 回答者： stomachman
  • 回答日時：

まずは回文の文法（生成規則）を書けばいいんです。

この回答への補足あり
    • good
    • 0
    • 件
通報する

No.2

回文は、NFAやMLBでは無理です。


この↓リンク先の下のほうに、そのことの証明があります。
https://hwb.ecc.u-tokyo.ac.jp/wp/applications-2/ …
ＰＤＡなら可能ですよ。
    • good
    • 0
    • 件
通報する

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう！

Q質問する（無料）

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

ページトップページトップ

Q質問する（無料）

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

おすすめ情報