精华内容
下载资源
问答
  • 形式语言与自动机 课后题答案
    千次阅读
    2020-06-14 20:10:17

    在这里插入图片描述
    考点:图灵机⇒语言

    解:工作过程:首先从 q 0 q_0 q0 将读入的0改为1,读头向右移动到状态 q 1 q_1 q1,然后;读入1则改为0读头向右移动回到状态 q 0 q_0 q0,若读入B则不变,读头向右移动到状态 q f q_f qf

    接收的语言:以0开头,后面10重复的字符串,其中10重复次数可为0。 L = 0 ( 10 ) n ∣ n ≥ 0 L={0(10)^n |n≥0} L=0(10)nn0
    在这里插入图片描述
    考点:图灵机⇒句子的识别过程(格局)

    解:识别 00001000 的过程:
    q 0 00001000 ├ M 0 q 0 0001000 ├ M 00 q 0 001000 ├ M 000 q 0 01000 ├ M 0000 q 0 1000 q_0 00001000├_{M} 0q_0 0001000├_{M} 00q_0 001000├_{M} 000q_0 01000├_{M} 0000q_0 1000 q000001000M0q00001000M00q0001000M000q001000M0000q01000

    ├ M 00001 q 1 000 ├ M 000010 q 1 00 ├ M 0000100 q 1 0 ├ M 00001000 q 1 B ├ M 00001000 B q 2 B ├_M 00001q_1 000├_M 000010q_1 00├_M 0000100q_1 0├_M 00001000q_1 B├_M 00001000Bq_2 B M00001q1000M000010q100M0000100q10M00001000q1BM00001000Bq2B

    识别10000的过程:
    q 0 10000 ├ M 1 q 1 0000 ├ M 10 q 1 000 ├ M 100 q 1 00 ├ M 1000 q 1 0 ├ M 10000 q 1 B ├ M 10000 B q 2 B q_0 10000├_{M}1q_1 0000├_{M} 10q_1 000├_{M} 100q_1 00├_{M} 1000q_1 0├_{M}10000q_1 B├_{M}10000Bq_2 B q010000M1q10000M10q1000M100q100M1000q10M10000q1BM10000Bq2B

    在这里插入图片描述
    考点:语言⇒图灵机(设计图灵机)

    解:(1)设计思路:遇到起始的1改为B右移,遇到起始的0改为B左移找第1个1改为B右移……若回去找1找不到且从头找0找不到,说明 n = m n=m n=m 则接收;若找0找不到,说明 n > m n>m nm 则接收,因此设计的图灵机为 M = ( { q 0 , q 1 , q 2 , q 3 , q 4 , q 5 } , { 0 , 1 } , { 0 , 1 , B , X , Y } , δ , q 0 , B , { q ( 3 ) , q 5 } ) M=(\{q_0,q_1,q_2,q_3,q_4,q_5 \},\{0,1\},\{0,1,B,X,Y\},δ,q_0,B,\{q_(3 ),q_5\}) M=({q0,q1,q2,q3,q4,q5},{0,1},{0,1,B,X,Y},δ,q0,B,{q(3),q5}),其中 δ δ δ 如下:
    在这里插入图片描述

    更多相关内容
  • 蒋宗礼形式语言自动机课后答案,答案是前四,网上至今没有流出五之后的答案,希望有能人志士可以补充后面的答案
  • 形式语言与自动机 第三章 课后题答案

    千次阅读 多人点赞 2020-06-04 21:06:41
    解:(1)M=({q0,q1,q2,q3},{a,b},δ,q0,{q3})M=(\{q_0,q_1,q_2,q_3\},\{a,b\},δ,q_0,\{q_3\})M=({q0​,q1​,q2​,q3​},{a,b},δ,q0​,{q3​}),其中 δ 如下: (2)M=({q0,q1,q2},{a,b},δ,q0,{q2})M=(\{q_0,q_...

    **在这里插入图片描述**
    考点:语言⇒DFA(设计DFA,记录关键信息

    解:(1) M = ( { q 0 , q 1 , q 2 , q 3 } , { a , b } , δ , q 0 , { q 3 } ) M=(\{q_0,q_1,q_2,q_3\},\{a,b\},δ,q_0,\{q_3\}) M=({q0,q1,q2,q3},{a,b},δ,q0,{q3}),其中 δ 如下:
    在这里插入图片描述
    (2) M = ( { q 0 , q 1 , q 2 } , { a , b } , δ , q 0 , { q 2 } ) M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_2\}) M=({q0,q1,q2},{a,b},δ,q0,{q2}),其中 δ 如下:
    在这里插入图片描述
    (3) M = ( { q 0 , q 1 , q 2 } , { a , b } , δ , q 0 , { q 2 } ) M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_2\}) M=({q0,q1,q2},{a,b},δ,q0,{q2}),其中 δ 如下:
    在这里插入图片描述
    (4) M = ( { q 0 , q 1 , q 2 } , { a , b } , δ , q 0 , { q 0 , q 1 , q 2 } ) M=(\{q_0,q_1,q_2\},\{a,b\},δ,q_0,\{q_0,q_1,q_2\}) M=({q0,q1,q2},{a,b},δ,q0,{q0,q1,q2}),其中 δ 如下:
    在这里插入图片描述

    在这里插入图片描述
    考点:NFA⇒DFA (子集构造法:始态出发,遇什么填什么)
    解:(1) D F A − M 1 = ( Q 1 , { a , b } , δ 1 , { q 0 } , { { q 0 , q 1 , q 3 } , { q 0 , q 2 , q 3 } , { q 0 , q 3 } , { q 0 , q 1 , q 2 , q 3 } ) , 其 中 Q 1 = { { q 0 } , { q 0 , q 1 } , { q 0 , q 1 , q 2 } , { q 0 , q 2 } , { q 0 , q 1 , q 2 , q 3 } , { q 0 , q 1 , q 3 } , { q 0 , q 2 , q 3 } , { q 0 , q 3 } } DFA-M_1=(Q_1,\{a,b\},δ_1,\{q_0\},\{ \{q_0,q_1,q_3 \},\{q_0,q_2,q_3 \},\{q_0,q_3 \},\{q_0,q_1,q_2,q_3\}),其中 Q_1=\{\{q_0\},\{q_0,q_1\},\{q_0,q_1,q_2\},\{q_0,q_2\},\{q_0,q_1,q_2,q_3\},\{q_0,q_1,q_3\},\{q_0,q_2,q_3\},\{q_0,q_3\}\} DFAM1=(Q1,{a,b},δ1,{q0},{{q0,q1,q3},{q0,q2,q3},{q0,q3},{q0,q1,q2,q3})Q1={{q0},{q0,q1},{q0,q1,q2},{q0,q2},{q0,q1,q2,q3},{q0,q1,q3},{q0,q2,q3},{q0,q3}}
    δ 1 δ_1 δ1 满足:
    在这里插入图片描述
    (2) D F A M 1 = ( { Q 1 , { a , b } , δ 1 , { q 0 } , { { q 1 } , { q 3 } , { q 1 , q 2 } , { q 0 , q 1 , q 2 } , { q 1 , q 3 } , { q 1 , q 2 , q 3 } , { q 2 , q 3 } ) DFA M_1=(\{Q_1,\{a,b\},δ_1,\{q_0\},\{\{q_1\},\{q_3\},\{q_1,q_2\},\{q_0,q_1,q_2\},\{q_1,q_3\},\{q_1,q_2,q_3\},\{q_2,q_3\}) DFAM1=({Q1,{a,b},δ1,{q0},{{q1},{q3},{q1,q2},{q0,q1,q2},{q1,q3},{q1,q2,q3},{q2,q3}),其中 Q 1 = { { q 0 } , { q 1 , q 3 } , { q 1 } , { q 2 } , { q 0 , q 1 , q 2 } , { q 1 , q 2 } , { q 3 } , { q 1 , q 2 , q 3 } , { q 2 , q 3 } } Q_1=\{ \{q_0\},\{q_1,q_3\},\{q_1\},\{q_2\},\{q_0,q_1,q_2\},\{q_1,q_2\},\{q_3\},\{q_1,q_2,q_3\},\{q_2,q_3\}\} Q1={{q0},{q1,q3},{q1},{q2},{q0,q1,q2},{q1,q2},{q3},{q1,q2,q3},{q2,q3}}
    δ 1 δ_1 δ1 满足:
    在这里插入图片描述
    在这里插入图片描述
    考点:文法⇒正则式 (R规则:设x→αx+β(x→αx|β),则x=α*β)
    解:(1)联立方程组:
    在这里插入图片描述
    将④带入③中得: B = b c B + b d + b B=bcB+bd+b B=bcB+bd+b,利用规则R,得 B = ( b c ) ∗ ( b d + b ) ⋅ ⋅ ⋅ ⋅ ⑤ B=(bc)^* (bd+b)····⑤ B=(bc)(bd+b)
    再将②和⑤带入①得: S = b a a S + b a b B + B S=baaS+babB+B S=baaS+babB+B
    = b a a S + ( b a b + ε ) B =baaS+(bab+ε)B =baaS+(bab+ε)B
    = b a a S + ( b a b + ε ) ( b c ) ∗ ( b d + b ) =baaS+(bab+ε) (bc)^* (bd+b) =baaS+(bab+ε)(bc)(bd+b)
    = ( b a a ) ∗ ( b a b + ε ) ( b c ) ∗ ( b d + b ) =(baa)^* (bab+ε) (bc)^* (bd+b) =(baa)(bab+ε)(bc)(bd+b)
    ∴得到正则式为 ( b a a ) ∗ ( b a b + ε ) ( b c ) ∗ ( b d + b ) (baa)^* (bab+ε) (bc)^* (bd+b) (baa)(bab+ε)(bc)(bd+b)

    (2)联立方程组:
    在这里插入图片描述
    由③和规则R得: B = b ∗ a ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⑥ B=b^* a······⑥ B=ba
    将⑤⑥带入④中得: C = d + a b b ∗ a = d + a b + a ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⑦ C=d+abb^* a=d+ab^+ a······⑦ C=d+abba=d+ab+a
    将⑥⑦带入②中得: A = c ( d + a b + a ) + b + a ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⑧ A=c(d+ab^+ a)+b^+ a······⑧ A=c(d+ab+a)+b+a
    将⑥⑧带入①中得: S = a c ( d + a b + a ) + a b + a + b ∗ a S=ac(d+ab^+ a)+ab^+ a+b^* a S=ac(d+ab+a)+ab+a+ba
    = a c d + a c a b + a + a b + a + b ∗ a =acd+acab^+ a+ab^+ a+b^* a =acd+acab+a+ab+a+ba
    ∴得到正则式为 a c d + a c a b + a + a b + a + b ∗ a acd+acab^+ a+ab^+ a+b^* a acd+acab+a+ab+a+ba

    在这里插入图片描述
    考点:自动机接受的语言;ε-NFA⇒NFA (先判断F,每步扩展空闭包)
    解:(1)矩阵对应的ε-NFA如下:
    在这里插入图片描述
    利用排除法有,共23个串: a a c , a b b , a b c , a c a , a c b , a c c , b a b , b a c , b b a , b b b , b b c , b c a , b c b , b c c , c a a , c a b , c a c , c b a , c b b , c b c , c c a , c c b , c c c aac,abb,abc,aca,acb,acc,bab,bac,bba,bbb,bbc,bca,bcb, bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc aac,abb,abc,aca,acb,acc,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc

    (2)因为 e c l o s u r e ( q 0 ) ∩ F = Ø eclosure(q0)∩F=Ø eclosure(q0)F=Ø,则 F 1 = F = { r } F_1=F=\{r\} F1=F={r},则 N F A − M = ( { p , q , r } , { a , b , c } , δ 1 , p , { r } ) NFA -M=(\{p,q,r\},\{a,b,c\},δ_1,p,\{r\}) NFAM=({p,q,r},{a,b,c},δ1,p,{r}),其中 δ 1 δ_1 δ1
    在这里插入图片描述
    在这里插入图片描述
    考点:正则集⇒右线性文法 (R规则逆用)
    解:(2)题目对应的正则表达式为 ( a + b ) ∗ a b b (a+b)^* abb (a+b)abb,逆用R规则得到对应的右线性文法为 G = ( { S } , { a , b } , P , S ) G=(\{S\},\{a,b\},P,S) G=({S},{a,b},P,S),其中P: S → ( a + b ) S ∣ a b b S→(a+b)S|abb S(a+b)Sabb,即 S → a S ∣ b S ∣ a b b S→aS|bS|abb SaSbSabb

    (4)题目对应的正则表达式为 ( a + b ) ∗ ( a a + b b ) ( a + b ) ∗ (a+b)^* (aa+bb)(a+b)^* (a+b)(aa+bb)(a+b),逆用R规则得到对应的右线性文法为 G = ( { S , A } , { a , b } , P , S ) G=(\{S,A\},\{a,b\},P,S) G=({S,A},{a,b},P,S),其中P为 S → ( a + b ) S ∣ a a A ∣ b b A , A → ( a + b ) A ∣ ε S→(a+b)S|aaA|bbA, A→(a+b)A|ε S(a+b)SaaAbbA,A(a+b)Aε,即 S → a S ∣ b S ∣ a a A ∣ b b A , A → a A ∣ b A ∣ ε S→aS|bS|aaA|bbA, A→aA|bA|ε SaSbSaaAbbA,AaAbAε

    在这里插入图片描述
    考点:正则集⇒右线性文法;正则集⇒ε-NAF(有限自动机);右线性文法⇒NFA
    解:(1)逆用R规则得到对应右线性文法 G = ( { S , A } , { a , b } , P , S ) G=(\{S,A\},\{a,b\},P,S) G=({S,A},{a,b},P,S),其中P为 S → a A , A → b a A ∣ ε S→aA,A→baA|ε SaA,AbaAε
    (2)由(1)中右线性文法有 S → ε ∉ P S→ε∉P Sε/P,则转换为 D F A − M = ( { S , A , H } , { a , b } , δ , S , { H } ) DFA-M=(\{S,A,H\},\{a,b\},δ,S,\{H\}) DFAM=({S,A,H},{a,b},δ,S,{H}),其中 δ δ δ为:
    对于产生式 S → a A S→aA SaA,有 δ ( S , a ) = { A } δ(S,a)=\{A\} δ(S,a)={A}
    对于产生式 A → b S A→bS AbS,有 δ ( A , b ) = { S } δ(A,b)=\{S\} δ(A,b)={S}
    对于产生式 A → ε A→ε Aε,有 δ ( A , ε ) = { H } δ(A,ε)=\{H\} δ(A,ε)={H}
    状态转移图如下:
    在这里插入图片描述
    继续进行化简,消去 ε ε ε,将状态A与H合并,得到下图:
    在这里插入图片描述
    在这里插入图片描述
    考点:DFA⇒最小状态DFA (填表法)
    解: E , F , G , H E,F,G,H E,F,G,H 为不可达状态,删去后利用填表法:
    在这里插入图片描述
    由表格得: B,C等价, { B , C } \{B,C\} {B,C} [ B ] [B] [B] 表示,则等价最小DFA的转移图为:
    在这里插入图片描述
    在这里插入图片描述
    考点:正则集的泵浦引理
    解:(1)L(G)中,a和b的个数相等。由泵浦引理,假设L是正则集,取足够大的整数 k, ω = a k ( c b ) k c , ∣ ω ∣ = 3 k + 1 > k , ∣ ω 0 ∣ > 0 , 0 < ∣ ω 1 ω 0 ∣ ≤ k ω=a^k (cb)^k c,|ω|=3k+1>k,|ω_0|>0,0<|ω_1ω_0|≤k ω=ak(cb)kcω=3k+1>k,ω0>00<ω1ω0k,则 ω 0 ω_0 ω0 只能处于 a k a^k ak 段。当 i ≠ 1 i≠1 i=1时,a的个数发生改变,而b的个数不会变,a的个数≠b的个数,因此与假设矛盾,则L(G)不是正则集。

    (3)由泵浦原理,假设L是正则集,取足够大的整数 k , ω = 0 k 1 2 k + 1 , ∣ ω ∣ = 2 k + 2 > k , ∣ ω 0 ∣ > 0 , 0 < ∣ ω 1 ω 0 ∣ ≤ k k,ω=0^k 12^{k+1},|ω|=2k+2>k,|ω_0 |>0,0<|ω_1 ω_0 |≤k k,ω=0k12k+1,ω=2k+2>k,ω0>00<ω1ω0k,限制了 ω 0 ω_0 ω0 只能在 0 k 0^k 0k 段。当 i = 0 i=0 i=0 时, ω 1 ω 0 0 ω 2 ω_1 ω_0^0 ω_2 ω1ω00ω2中0的数量减少,而1和2的个数没变,不满足 0 n 1 m 2 n + m 0^n 1^m 2^{n+m} 0n1m2n+m。与假设矛盾,L不是正则集。

    (4)由泵浦原理,假设L是正则集,取足够大的整数 k , ω = a k b a k b , ∣ ω ∣ = 2 k + 2 > k , ∣ ω 0 ∣ > 0 , 0 < ∣ ω 1 ω 0 ∣ ≤ k k,ω=a^k ba^k b,|ω|=2k+2>k,|ω_0 |>0,0<|ω_1 ω_0 |≤k kω=akbakbω=2k+2>kω0>00<ω1ω0k,限制了 ω 0 ω_0 ω0 只能处于 a k a^k ak 段。当 i ≠ 0 i≠0 i=0 时, a k a^k ak 段中a的个数发生改变,不等于k,不满足 ωω 的形式。与假设矛盾,L不是正则集。

    在这里插入图片描述
    考点:正则集的泵浦引理;设计正则式
    解:(1)首先根据题意设计DFA,0、1的奇偶性需要4个状态来记录,因此容易得出DFA如下:
    在这里插入图片描述
    再利用状态消去的形式化方法,将DFA转换为正则式:
    首先加初态s和终态a,与原自动机相,扩展为广义自动机:
    在这里插入图片描述
    接下来逐个消去中间状态,消去 q 1 q_1 q1
    在这里插入图片描述
    得到自动机:
    在这里插入图片描述
    最终得到正则式为 0 + ( 11 ) + 0 + ( 10 + ( 11 ) + 10 ) ( 01 ( 11 ) ∗ 10 ) ∗ ( 1 + 01 ( 11 ) ∗ 0 ) ( 0 ( 11 ) ∗ 0 + ( 1 + 0 ( 11 ) ∗ 10 ) ( 01 ( 11 ) ∗ 10 ) ∗ ( 1 + 01 ( 11 ) ∗ 0 ) ) ∗ 0+(11)^+ 0+(10+(11)^+ 10)(01(11)^* 10)^* (1+01(11)^* 0)(0(11)^* 0+(1+0(11)^* 10)(01(11)^* 10)^* (1+01(11)^* 0))^* 0+(11)+0+(10+(11)+10)(01(11)10)(1+01(11)0)(0(11)0+(1+0(11)10)(01(11)10)(1+01(11)0))

    (2)由泵浦引理,假设L为正则集,取 ω = a 2 p b p , ∣ ω ∣ = ∣ ω 1 ω 0 ω 2 ∣ = 3 p > p , 0 < ∣ ω 1 ω 0 ∣ ≤ p ω=a^{2p} b^p,|ω|=|ω_1ω_0ω_2|=3p>p,0<|ω_1ω_0|≤p ω=a2pbp,ω=ω1ω0ω2=3pp,0ω1ω0p,因此限制了 ω 1 ω 0 ω_1ω_0 ω1ω0 只能在 a 2 p a^{2p} a2p 段,当 i = 0 i=0 i=0 时,a部分的长度减小,但b部分长度不变,a个数≠b个数,不符合L,与假设矛盾,因此L不是正则集。

    在这里插入图片描述
    考点:有限自动机⇒正则式 (状态消去形式化方法)
    解:(a)使用状态消去形式化方法,消去 q 1 q_1 q1,得到状态图:
    在这里插入图片描述
    直接得到正则式为 ( a + b ( b + a b ) ∗ a a ) ∗ (a+b(b+ab)^* aa)^* (a+b(b+ab)aa)

    (b)用形式化消去法,扩展为广义自动机有:
    在这里插入图片描述
    消去状态 q 0 q_0 q0 有:
    在这里插入图片描述
    消去状态 q 1 q_1 q1 有:
    在这里插入图片描述
    由此可直接写出正则式: a ( a a ) ∗ + ( b + a ( a a ) ∗ ( b + a b ) ) ( b b + ( a + b a ) ( a a ) ∗ ( b + a b ) ) ∗ ( ε + ( a + b a ) ( a a ) ∗ ) a(aa)^*+(b+a(aa)^* (b+ab)) (bb+(a+ba) (aa)^* (b+ab))^* (ε+(a+ba)(aa)^*) a(aa)+(b+a(aa)(b+ab))(bb+(a+ba)(aa)(b+ab))(ε+(a+ba)(aa))

    在这里插入图片描述
    考点:构造米兰机和摩尔机;米兰机与摩尔机的相互转换
    解:构造摩尔机 M 1 = ( { q 1 , q 2 , q 3 , q 4 , q 5 } , { a , b } , { 1 , 2 , 3 } , δ , g , q 0 ) M_1=(\{q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{1,2,3\},δ,g,q_0) M1=({q1,q2,q3,q4,q5},{a,b},{1,2,3},δ,g,q0),其中 δ , g δ,g δ,g 如下:
    在这里插入图片描述
    直接将摩尔机转换为米兰机有(将状态中的输出放到弧上) M 2 = ( { q 1 , q 2 , q 3 , q 4 , q 5 } , { a , b } , { 1 , 2 , 3 } , δ , g , q 0 ) M_2=(\{q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{1,2,3\},δ,g,q_0) M2=({q1,q2,q3,q4,q5},{a,b},{1,2,3},δ,g,q0)
    在这里插入图片描述

    展开全文
  • 形式语言与自动机理论--(蒋宗礼PPT学习教案.pptx
  • 形式语言与自动机理论(第3版) 蒋宗礼 姜守旭 编著 清华大学出版社。 课后1 、2、3、4答案,可以打印
  • 形式语言与自动机理论--(蒋宗礼PPT学习教案.pptx
  • 新版形式语言与自动机第三章的答案,是北邮版的教材。
  • 形式语言与自动机理论(2版) 蒋宗礼 课后答案[1-12].pdf
  • 形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版.形式语言与自动机理论-peter linz 第三版中文版.
  • 形式语言与自动机理论试题答案解析.doc
  • 形式语言与自动机 课后题答案

    千次阅读 多人点赞 2020-06-05 10:48:19
    形式语言与自动机 课后题答案

    在这里插入图片描述
    考点:文法⇒推导树

    解:(1)

    在这里插入图片描述
    (2)
    在这里插入图片描述
    (3)

    在这里插入图片描述

    在这里插入图片描述
    考点:文法⇒最左/右推导

    解:最左推导: E ⇒ l m E + T ⇒ l m T + T ⇒ l m F + T ⇒ l m b + T ⇒ l m b + T / F ⇒ l m b + F / F ⇒ l m b + b / F ⇒ l m b + b / b E⇒_{lm} E+T⇒_{lm} T+T⇒_{lm} F+T⇒_{lm} b+T⇒_{lm} b+T/F⇒_{lm} b+F/F⇒_{lm} b+b/F⇒_{lm} b+b/b ElmE+TlmT+TlmF+Tlmb+Tlmb+T/Flmb+F/Flmb+b/Flmb+b/b

    最右推导: E ⇒ r m E + T ⇒ r m E + T / F ⇒ r m E + T / b ⇒ r m E + F / b ⇒ r m E + b / b ⇒ r m T + b / b ⇒ r m F + b / b ⇒ r m b + b / b E⇒_{rm} E+T⇒_{rm} E+T/F⇒_{rm} E+T/b⇒_{rm} E+F/b⇒_{rm} E+b/b⇒_{rm} T+b/b⇒_{rm} F+b/b⇒_{rm} b+b/b ErmE+TrmE+T/FrmE+T/brmE+F/brmE+b/brmT+b/brmF+b/brmb+b/b

    在这里插入图片描述
    考点:文法二义性证明
    解:画出语言 a a a b a aaaba aaaba 的2颗推导树如下:
    在这里插入图片描述
    在这里插入图片描述
    同一文法可画出2个不同的推导树,因此该文法具有二义性。

    在这里插入图片描述
    考点:语言⇒上下文无关文法(设计上下文无关文法)

    解:(1)考虑在产生相同数目的0,1后,再生成多余的1.
    G = ( { S } , { 0 , 1 } , P , S ) G=(\{S\},\{0,1\},P,S) G=({S},{0,1},P,S),其中P为: S → 1 S 0 ∣ 1 S ∣ 10 S→1S0|1S|10 S1S01S10

    (2)考虑将0和1的部分拆开 G = ( { S , A } , { 0 , 1 } , P , S ) G=(\{S,A\},\{0,1\},P,S) G=({S,A},{0,1},P,S),其中P为:
    S → 1 A 1 ∣ 1 S 1 S→1A1|1S1 S1A11S1
    A → 00 A ∣ 00 A→00A|00 A00A00(服务 0 2 m 0^{2m} 02m

    (3)考虑将语言拆为2部分 G = ( { S , A , B } , { 0 , 1 } , P , S ) G=(\{S,A,B\},\{0,1\},P,S) G=({S,A,B},{0,1},P,S),其中P为:
    S → A B S→AB SAB(拆为2部分)
    A → 1 A 0 ∣ 10 A→1A0|10 A1A010
    B → 1 B 0 ∣ 10 B→1B0|10 B1B010

    在这里插入图片描述
    考点:消除无用符号

    解:(1)首先使用算法1,得到非生成符号C,删去C及其生成式有:
    S → E D S→ED SED

    D → a D→a Da

    E → b E→b Eb

    使用算法2,发现没有不可达符号,因此等价文法为: G = ( { S , D , E } , { a , b } , P , S ) G=(\{S,D,E\},\{a,b\},P,S) G=({S,D,E},{a,b},P,S),其中P:
    S → E D S→ED SED

    D → a D→a Da

    E → b E→b Eb

    (2)首先使用算法1,得到非生成符号C,删去C及其生成式有:
    S → D S→D SD

    D → b S ∣ b D→bS|b DbSb

    E → D S ∣ b E→DS|b EDSb

    使用算法2,发现不可达符号E,删去E及其生成式。因此等价文法为: G = ( { S , D } . { b } , P , S ) G=(\{S,D\}.\{b\},P,S) G=({S,D}.{b},P,S),其中P:
    S → D S→D SD

    D → b S ∣ b D→bS|b DbSb

    在这里插入图片描述
    考点:消空产生式

    解:根据算法得,可得致空符号有: D 、 E 、 C 、 S D、E、C、S DECS S S S 也为致空符号,因此加入 S 1 → S ∣ ε S_1→S|ε S1Sε,对于 S → D C E S→DCE SDCE 有: S → D C E ∣ C E ∣ D E ∣ D C ∣ D ∣ C ∣ E S→DCE|CE|DE|DC|D|C|E SDCECEDEDCDCE。因此消空后的等价文法为: G 1 = ( { S 1 , S , C , D , E } , { a , b } , P , S 1 ) G_1=(\{S_1,S,C,D,E\},\{a,b\},P,S_1) G1=({S1,S,C,D,E},{a,b},P,S1),其中 P P P
    S 1 → S ∣ ε S_1→S|ε S1Sε

    S → D C E ∣ C E ∣ D E ∣ D C ∣ D ∣ C ∣ E S→DCE|CE|DE|DC|D|C|E SDCECEDEDCDCE

    D → C C ∣ C D→CC|C DCCC

    C → E E ∣ E ∣ b C→EE|E|b CEEEb

    E → D D ∣ D ∣ a E→DD|D|a EDDDa

    在这里插入图片描述
    考点:简化CFG(消无用→消空→消单→消无用 )

    解:首先消无用符号,利用算法1发现没有非生成符号,再利用算法2也没有发现不可达符号。

    再消致空符号,利用算法发现所有符号都为致空符号。 S S S 为致空符号,因此将 S 1 → S ∣ ε S_1→S|ε S1Sε 加入P,P变为:
    S 1 → S ∣ ε S_1→S|ε S1Sε

    S → A 1 ∣ A 2 S→A_1 |A_2 SA1A2

    A 1 → A 3 ∣ A 4 A_1→A_3 |A_4 A1A3A4

    A 2 → A 4 ∣ A 5 A_2→A_4 |A_5 A2A4A5

    A 3 → S ∣ b A_3→S|b A3Sb

    A 4 → S ∣ a A_4→S|a A4Sa

    A 5 → S ∣ d A_5→S|d A5Sd

    再消除单产生式,构造 N S , N A i , i = 1 , 2 , 3 , 4 , 5 N_S,N_{A_i},i=1,2,3,4,5 NS,NAi,i=1,2,3,4,5,产生式的关系如下图:
    在这里插入图片描述
    因此P为:
    S 1 → a ∣ b ∣ d ∣ ε S_1→a|b|d|ε S1abdε

    S → a ∣ b ∣ d S→a|b|d Sabd

    A 1 → a ∣ b ∣ d A_1→a|b|d A1abd

    A 2 → a ∣ b ∣ d A_2→a|b|d A2abd

    A 3 → a ∣ b ∣ d A_3→a|b|d A3abd

    A 4 → a ∣ b ∣ d A_4→a|b|d A4abd

    A 5 → a ∣ b ∣ d A_5→a|b|d A5abd

    最后消去无用符号,利用算法1发现没有非生成符号;再用算法2发现只有 S 1 S_1 S1 为可达符号,删去其他符号及其产生式得到文法 G 1 = ( { S 1 } , { a , b , d } , P , S 1 ) G_1=(\{S_1 \},\{a,b,d\},P,S_1) G1=({S1},{a,b,d},P,S1),其中P为 S 1 → a ∣ b ∣ d ∣ ε S_1→a|b|d|ε S1abdε

    在这里插入图片描述
    考点:转换为CNF(Chomsky范式)

    解:首先删除无用符号,利用算法1发现没有非生成符号,再利用算法2发现没有不可达符号;
    再删除致空符号,利用算法发现S为致空符号,将 S 1 → ε ∣ S S_1→ε|S S1εS加入到P中,此时P为:
    S 1 → ε ∣ S S_1→ε|S S1εS

    S → A S B ∣ A B S→ASB|AB SASBAB

    A → a A S ∣ a A ∣ a A→aAS|aA|a AaASaAa

    B → S B S ∣ S B ∣ B S ∣ A ∣ b b B→SBS|SB|BS|A|bb BSBSSBBSAbb

    再消单产生式,单产生式有: S 1 → S , B → A S_1→S,B→A S1S,BA,因此此时P变为:
    S 1 → ε ∣ A S B ∣ A B S_1→ε|ASB|AB S1εASBAB

    S → A S B ∣ A B S→ASB|AB SASBAB

    A → a A S ∣ a A ∣ a A→aAS|aA|a AaASaAa

    B → S B S ∣ B S ∣ S B ∣ b b ∣ a A S ∣ a A ∣ a B→SBS|BS|SB|bb|aAS|aA|a BSBSBSSBbbaASaAa

    再消去无用符号,利用算法1、2发现没有无用符号。
    最后转换为CNF:对 S 1 → ε ∣ A B , S → A B , A → a , B → B S ∣ S B ∣ a S_1→ε|AB,S→AB,A→a,B→BS|SB|a S1εAB,SAB,Aa,BBSSBa 为CNF,加入到P中。
    S 1 → A S B S_1→ASB S1ASB 变换为 S 1 → A C , C → S B S_1→AC,C→SB S1AC,CSB
    S → A S B S→ASB SASB 变换为 S → A C S→AC SAC
    A → a A S ∣ a A A→aAS|aA AaASaA 变换为 A → E D , A → E A , D → A S , E → a A→ED,A→EA,D→AS,E→a AEDAEADASEa
    B → S B S ∣ a A S ∣ a A ∣ b b B→SBS|aAS|aA|bb BSBSaASaAbb 变换为 B → C S , B → E D , B → E A , B → F F , F → b B→CS,B→ED,B→EA,B→FF,F→b BCSBEDBEABFFFb

    由此得到文法 G 1 = ( { S 1 , S , A , B , C , D , E , F } , { a , b } , P 1 , S 1 ) G1=(\{S_1,S,A,B,C,D,E,F\},\{a,b\},P_1,S_1) G1=({S1,S,A,B,C,D,E,F},{a,b},P1,S1),其中 P 1 P_1 P1 为:
    S 1 → A B ∣ ε ∣ A C S_1→AB|ε|AC S1ABεAC

    S → A B ∣ A C S→AB|AC SABAC

    A → E D ∣ E A ∣ a A→ED|EA|a AEDEAa

    B → B S ∣ S B ∣ a ∣ C S ∣ E D ∣ E A ∣ F F B→BS|SB|a|CS|ED|EA|FF BBSSBaCSEDEAFF

    C → S B C→SB CSB

    D → A S D→AS DAS

    E → a E→a Ea

    F → b F→b Fb
    在这里插入图片描述
    考点:转换为CNF(Chomsky范式)

    解:先消除无用符号,利用算法1、2发现没有无用符号;再消致空符号,利用算法发现致空符号为A,B,因此P变为:
    S → 0 B B ∣ 0 B ∣ 1 A A ∣ 1 A ∣ 0 ∣ 1 S→0BB|0B|1AA|1A|0|1 S0BB0B1AA1A01

    B → 0 B 0 ∣ 00 B→0B0|00 B0B000

    A → 11 A ∣ 11 A→11A|11 A11A11

    此时没有单产生式和无用符号,转换为CNF: S → 0 ∣ 1 S→0|1 S01为CNF,加入到P中
    S → 0 B B S→0BB S0BB 变换为 S → C B , C → D B , D → 0 S→CB,C→DB,D→0 SCBCDBD0
    S → 0 B S→0B S0B 变换为 S → D B S→DB SDB
    S → 1 A A S→1AA S1AA 变换为 S → E A S→EA SEA E → F A E→FA EFA F → 1 F→1 F1
    S → 1 A S→1A S1A 变换为 S → F A S→FA SFA
    B → 0 B 0 B→0B0 B0B0 变换为 B → C D B→CD BCD
    B → 00 B→00 B00 变换为 B → D D B→DD BDD
    A → 11 A A→11A A11A 变换为 A → F E A→FE AFE
    A → 11 A→11 A11 变换为 A → F F A→FF AFF

    由此得到的文法为: G 1 = ( { S , A , B , C , D , E , F , G } , { 0 , 1 } , P 1 , S ) G1=(\{S,A,B,C,D,E,F,G\},\{0,1\},P_1,S) G1=({S,A,B,C,D,E,F,G},{0,1},P1,S),其中 P 1 P_1 P1 如下:
    S → C B ∣ D B ∣ E A ∣ F A ∣ 0 ∣ 1 S→CB|DB|EA|FA|0|1 SCBDBEAFA01

    A → F E ∣ F F A→FE|FF AFEFF

    B → C D ∣ D D B→CD|DD BCDDD

    C → D B C→DB CDB

    D → 0 D→0 D0

    E → F A E→FA EFA

    F → 1 F→1 F1

    在这里插入图片描述
    考点:转换为GNF(Greibach范式)

    解:题给产生式为CNF,N排序为 S , D S,D S,D,其中D为高位,第2个式子右边首符序号>左边的N,需要变换,将1式代入2式中有: D → D D S ∣ a S ∣ b D→DDS|aS|b DDDSaSb

    消除直接左递归, D → a S ∣ b ∣ a s D ′ ∣ b D ′ , D ′ → D S ∣ D S D ′ D→aS|b|asD'|bD',D'→DS|DSD' DaSbasDbD,DDSDSD

    进行回代,此时N排序为 D ′ , S , D D',S,D D,S,D,其中D为高位:
    D ’ D’ D 回代入 S S S S → a S D ∣ b D ∣ a S D ′ D ∣ b D ′ D ∣ a S→aSD|bD|aSD'D|bD'D|a SaSDbDaSDDbDDa
    D D D 回代入 D ’ D’ D D ′ → a S S ∣ b S ∣ a s D ′ S ∣ b D ′ S ∣ a S S D ′ ∣ b S D ′ ∣ a s D ′ S D ′ ∣ b D ′ S D ′ D'→aSS|bS|asD'S|bD'S|aSSD'|bSD'|asD' SD'|bD'SD' DaSSbSasDSbDSaSSDbSDasDSDbDSD

    在这里插入图片描述
    考点:2 型文法⇒PDA

    解:(1)
    在这里插入图片描述
    (2)
    在这里插入图片描述
    在这里插入图片描述
    考点:语言⇒文法(设计文法);文法的二义性

    解: G = ( { S , A , B , C , D } , a , b , c , P , S ) G=(\{S,A,B,C,D\},{a,b,c},P,S) G=({S,A,B,C,D},a,b,c,P,S)
    S → A D ∣ B C S→AD|BC SADBC

    A → a A ∣ ε A→aA|ε AaAε

    B → a B b ∣ ε B→aBb|ε BaBbε

    C → c C ∣ ε C→cC|ε CcCε

    D → b D c ∣ ε D→bDc|ε DbDcε
    有二义性,当 i = j = k i=j=k i=j=k 时,存在 2 颗推导树,如 a b c ∈ L abc∈L abcL
    在这里插入图片描述
    在这里插入图片描述
    考点:泵浦引理

    解:(1)假设是 CFL。利用泵浦引理,取常数 p, ω = 0 p 2 1 p , ∣ ω ∣ = p 2 + p ≥ p ω=0^{p^2}1^p,|ω|=p^2+p≥p ω=0p21pω=p2+pp,将 ω 写为 ω 1 ω 2 ω 0 ω 3 ω 4 ω_1ω_2ω_0ω_3ω_4 ω1ω2ω0ω3ω4,其中 ω 2 ω 3 ≠ ε ω_2ω_3≠ε ω2ω3=ε ∣ ω 2 ω 0 ω 3 ∣ ≤ p |ω_2ω_0ω_3|≤p ω2ω0ω3p,下面考虑 ω 2 ω 0 ω 3 ω_2ω_0ω_3 ω2ω0ω3 ω ω ω 中所处的位置:
    ①当 ω 2 , ω 3 ω_2,ω_3 ω2,ω3 都只包含 0 (1 同理) 时, ω 1 ω 2 0 ω 0 ω 3 0 ω 4 ω_1ω_2^0 ω_0ω_3^0ω_4 ω1ω20ω0ω30ω4 的 0 部分长度减少,1 部分长度不变,明显不属于 L,与 CFL 的假设矛盾。
    ②当 ω 2 , ω 3 ω_2,ω_3 ω2,ω3 自身不能横跨 0 p 2 1 p 0^{p^2}1^p 0p21p时,否则 01 顺序会乱,因此只能是 ω 2 ω_2 ω2 在0 部分, ω 3 ω_3 ω3在 1 部分。假设 | ω 2 ∣ = k 1 ≥ 1 , ∣ ω 3 ∣ = k 2 ≥ 1 ω_2|=k_1≥1,|ω_3|=k_2≥1 ω2=k11,ω3=k21,则取 ω 1 ω 2 0 ω 0 ω 3 0 ω 4 , ( p − k 2 ) 2 ≤ ( p − 1 ) 2 = p 2 − 2 p + 1 < p 2 − k 1 ω_1ω_2^0 ω_0ω_3^0ω_4, (p-k_2)^2≤(p-1)^2=p^2-2p+1<p^2-k_1 ω1ω20ω0ω30ω4(pk2)2(p1)2=p22p+1<p2k1。因此 ω ∉ L ω∉L ω/L,与 CFL 的假设矛盾。
    综上所述,不是 CFL。

    (5)假设是 CFL,利用泵浦引理。取常数 p, ω = x x ω=xx ω=xx ω = 0 p 1 p 0 p 1 p , ∣ ω ∣ = 4 p ≥ p ω=0^p 1^p 0^p 1^p,|ω|=4p≥p ω=0p1p0p1pω=4pp,将 ω ω ω 写为 ω 1 ω 2 ω 0 ω 3 ω 4 ω_1ω_2ω_0ω_3ω_4 ω1ω2ω0ω3ω4,其中 ω 2 ω 3 ≠ ε ω_2ω_3≠ε ω2ω3=ε ∣ ω 2 ω 0 ω 3 ∣ ≤ p |ω_2ω_0ω_3|≤p ω2ω0ω3p。下面考虑 ω 2 ω 0 ω 3 ω_2ω_0ω_3 ω2ω0ω3 ω ω ω 中所处的位置:
    ①当 ω 2 , ω 3 ω_2,ω_3 ω2,ω3 位于同一 0(1 同理)时, ω 1 ω 2 0 ω 0 ω 3 0 ω 4 ω_1ω_2^0 ω_0ω_3^0ω_4 ω1ω20ω0ω30ω4 ω 2 , ω 3 ω_2,ω_3 ω2,ω3 部分长度减少,明显不属于L,与 CFL 的假设矛盾;
    ②当 ω 2 ω 0 ω 3 ω_2ω_0ω_3 ω2ω0ω3 横跨0和1时, ω 1 ω 2 0 ω 0 ω 3 0 ω 4 ω_1ω_2^0 ω_0ω_3^0ω_4 ω1ω20ω0ω30ω4 ω 2 , ω 3 ω_2,ω_3 ω2,ω3 所在部分长度改变 ≠ p ≠p =p,明显不属于L,与 CFL 的假设矛盾;
    综上所述,不是 CFL。

    在这里插入图片描述
    考点:设计 PDA

    解:(1)
    在这里插入图片描述
    (2)
    在这里插入图片描述
    (3)
    在这里插入图片描述
    (4)容易写出文法: S → 0 S 1 ∣ 0 S 11 ∣ ε S→0S1|0S11|ε S0S10S11ε,将文法转换为 PDA:
    在这里插入图片描述

    (5)
    在这里插入图片描述
    q 1 q_1 q1 表示 1 的个数>0 的个数, q 2 q_2 q2 表示 0 的个数>1 的个数

    展开全文
  • 形式语言与自动机蒋宗礼书籍,讲义和课后题答案,课后答案非常难找
  • Turing Machine 图灵机 下推自动机类似,都有七个部分,不过栈的符号集合转变为taple集合,转移函数对taple进行操作,并且b是一个空字符, 瞬时表如下 图灵机接受的语言叫递归...以上为第三章内容,主要讲解了图...

    Turing Machine
    图灵机
    在这里插入图片描述
    与下推自动机类似,都有七个部分,不过栈的符号集合转变为taple集合,转移函数对taple进行操作,并且b是一个空字符,
    瞬时表如下
    在这里插入图片描述
    图灵机接受的语言叫递归可枚举语言

    在这里插入图片描述
    在这里插入图片描述
    以上为递归语言的定义
    在这里插入图片描述
    递归语言的性质
    在这里插入图片描述
    乔布斯及语法的四种类型
    在这里插入图片描述
    线程绑定的自动机,非确定性图灵机
    在这里插入图片描述
    右线程语法
    在这里插入图片描述
    左线程语法
    在这里插入图片描述
    等价状态和可区分状态

    在这里插入图片描述
    以上为第三章内容,主要讲解了图灵机以及递归可枚举语言的使用。

    展开全文
  • 北邮形式语言与自动机章可够习题答案
  • 形式语言与自动机.rar

    2019-08-20 13:33:19
    第3章 有穷自动机 3.1 非形式化描述 3.2 有穷自动机的基本定义 3.3 非确定的有穷自动机 3.4 具有£转移的有穷自动机 3.5 有穷自动机的应用 3.5.1 在文本中查找字符串 3.5.2 用于文本搜索的非确定的有穷...
  • 形式语言 语言概述 语言描述(该语言是什么样的,句子是否属于该语言)的种途径: 穷举法(把语言中的所有句子都枚举出来)——只适合句子数目有限的语言; 文法描述(语言中的每个句子用严格定义的规则来构造)...
  • P37 4、6、7课后题答案
  • 形式语言与自动机理论--第三章 有限状态自动机的ppt
  • 北邮 形式语言与自动机

    千次阅读 多人点赞 2020-06-29 11:37:08
    本文总结 BUPT 计算机学院《形式语言与自动机》的学习资料,希望能帮到学弟学妹,打好基础。 从名字也能知道,这门课就是学形式化语言及其对应的自动机。这门课相对简单,知识脉络十分清晰。总结一下就是很简单。 ...
  • 形式语言与自动机》(王柏、杨娟编著)课后习题答案
  • 第二 目录 2.1 有穷自动机(有限自动机) 我们来回顾一下文法与自动机的区别: 文法:对语言的有穷说明 识别器:有穷的说明无穷语言的一种方法,最简单的识别器就是有穷自动机 ...第三项:得儿塔...
  • 这是我这学期学习形式语言与自动机原理的知识点及一点点体会,课本对应蒋宗礼第三版,
  • 网络下载,回归网络,《形式语言与自动机理论》习题答案
  • 第三章 图灵机(更高级的形式化手法) 一、 语言及文法 文法系统——一类生成系统 1.1 文法的形式概念 字母表: 字符的有限集合——字母表T 例T={a…z, A…Z, 0…9, +, -, …} 字母表的成员不一定必须是单个的字.....
  • 国科大《自然语言处理》2020春季学期课程学习笔记,第三章形式语言与自动机
  • 形式语言与自动机第三课 本章节主要内容: 确定有限自动机、非确定有限自动机及其等价性 右线性文法和有限自动机的等价性 右线性文法性质(泵普定理) 使用归纳法进行证明 确定有限自动机、非确定有限自动机及其...
  • 文章目录图灵机1 定义:2 动作3 瞬时描述 图灵机 1 定义: 2 动作 解释一下:当前状态为q,读头符合为X,现将读头符号从X替换为Y,向左移动一格,状态转换为p。下面来看一个例子: 上面是状态转移图的形式,下面...
  • 1~3章
  • 形式语言与自动机答案

    热门讨论 2009-06-06 10:52:03
    这是自动机理论、语言与计算导论(二版)的2-7部分课后题答案。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,361
精华内容 2,144
关键字:

形式语言与自动机第三章