跳到主要内容

千葉大学 理学研究科 基盤理学専攻 数学・情報数理学コース 2013年8月実施 専門 B12

标签：

Author​

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

Description​

決定性有限オートマトン (Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) に対し、β,γ:Q×Σ∗→Q\beta,\gamma:Q\times\Sigma^*\to Q を次で定める。a∈Σ,w∈Σ∗a\in\Sigma,w\in\Sigma^* とする。

β(q,ε)=q,β(q,wa)=δ(β(q,w),a),γ(q,ε)=q,γ(q,aw)=γ(δ(q,a),w).\begin{aligned} \beta(q,\varepsilon)&=q,&\beta(q,wa)&=\delta(\beta(q,w),a),\\ \gamma(q,\varepsilon)&=q,&\gamma(q,aw)&=\gamma(\delta(q,a),w). \end{aligned}

(1) β(q,aw)=β(δ(q,a),w)\beta(q,aw)=\beta(\delta(q,a),w) を帰納法で示せ。何についての帰納法か明記せよ。

(2) β(q,w)=γ(q,w)\beta(q,w)=\gamma(q,w) を示せ。

题目描述​

对确定性有限自动机定义上述两种扩展转移函数。(1) 用归纳法证明 β(q,aw)=β(δ(q,a),w)\beta(q,aw)=\beta(\delta(q,a),w)，明确归纳变量。(2) 证明两种定义对所有状态与词都给出相同结果。

Kai​

(1)​

∣w∣|w| に関して、すべての q,aq,a について同時に帰納法を用いる。w=εw=\varepsilon なら両辺は δ(q,a)\delta(q,a)。長さ nn の語で成立すると仮定し、w=vbw=vb、∣v∣=n|v|=n、b∈Σb\in\Sigma とすると

β(q,avb)=δ(β(q,av),b)=δ(β(δ(q,a),v),b)=β(δ(q,a),vb).\begin{aligned} \beta(q,avb) &=\delta(\beta(q,av),b)\\ &=\delta(\beta(\delta(q,a),v),b) =\beta(\delta(q,a),vb). \end{aligned}

よってすべての語で成立する。

(2)​

再び ∣w∣|w| について、すべての qq に対して同時に帰納法を用いる。空語では両辺は qq。w=avw=av のとき、(1) と帰納法の仮定より

β(q,av)=β(δ(q,a),v)=γ(δ(q,a),v)=γ(q,av).\beta(q,av)=\beta(\delta(q,a),v) =\gamma(\delta(q,a),v)=\gamma(q,av).
本页目录