跳到主要内容

千葉大学 融合理工学府 数学情報科学専攻 数学・情報数理学コース 2022年8月実施 専門 B11

标签：

Author​

祭音Myyura (co-authored with GPT 6 Astra)

Description​

Σ\Sigma は空でない有限アルファベット、L,L1,L2⊆Σ∗L,L_1,L_2\subseteq\Sigma^* は正則言語とする。次の言語が正則であることを示せ。

  1. L1△L2L_1\triangle L_2。
  2. {w:∃v∈L1, vw∈L2}\{w:\exists v\in L_1,\ vw\in L_2\}。
  3. {w:∃n≥0, ∃w0,…,wn,v1,…,vn, w=w0⋯wn, w0v1w1⋯vnwn∈L}\{w:\exists n\ge0,\ \exists w_0,\ldots,w_n,v_1,\ldots,v_n,\ w=w_0\cdots w_n,\ w_0v_1w_1\cdots v_nw_n\in L\}。

题目描述​

设 L,L1,L2L,L_1,L_2 为正则语言，证明以下语言正则：(1) 对称差；(2) 存在前缀 v∈L1v\in L_1 使 vw∈L2vw\in L_2 的所有 ww；(3) 从 LL 中的词删除若干连续片段后得到的所有词。

Kai​

(1) L1,L2L_1,L_2 を受理する完全 DFA の直積をとり、成分のちょうど一方が受理状態となる状態を受理状態に指定する。これが対称差を受理する。

(2) L2L_2 の DFA を (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) とし、

I={δ∗(q0,v):v∈L1}⊆QI=\{\delta^*(q_0,v):v\in L_1\}\subseteq Q

とおく。初期状態を集合 II とする NFA（または新初期状態から II の各状態へ ϵ\epsilon 遷移を付けたもの）は、ある v∈L1v\in L_1 を読み終えた状態から ww を読んで受理できる場合に限り受理する。これは求める言語である。

(3) LL を受理する有限オートマトンの各文字遷移 q→arq\xrightarrow{a}r に、同じ始点・終点の ϵ\epsilon 遷移を追加する。この遷移は元の語の文字 aa を読み飛ばすことに対応する。従って新オートマトンが受理する語は、LL の語から任意の文字を削除して得る部分列全体である。削除した文字を連続する区間ごとにまとめれば、問題の v1,…,vnv_1,\ldots,v_n に一致する。よって求める言語は正則である。

本页目录