有限自动机理论章下推自动机

有限自动机理论章下推自动机第1页，课件共166页，创作于2023年2月FA只能处理正则语言正则文法生成无穷语言是由于A->wA不需要记录w的个数第2页，课件共166页，创作于2023年2月无关文法生成无穷语言

A->αAβ

需要记录α和β之间的对应关系无法用FA的有穷个状态来表示。第3页，课件共166页，创作于2023年2月为FA扩充一个无限容量的栈用栈的内容和FA的状态结合起来就可以表示无限存储。这种模型就是下推自动机PDA第4页，课件共166页，创作于2023年2月PDA作为形式系统最早于1961年出现在Oettinger

的论文中。与上下文无关文法的等价性由Chomsky于1962年发现。第5页，课件共166页，创作于2023年2月与FA比较PDA具有一个栈存储器有两个操作：入栈---将内容压入栈中

出栈---将栈顶元素移出第6页，课件共166页，创作于2023年2月下推自动机物理模型a1a2a3…aj…anan+1…FSC…存储带栈存储器第7页，课件共166页，创作于2023年2月栈存储器

存放不同于字母的符号只能对栈顶元素进行操作。第8页，课件共166页，创作于2023年2月下推自动机动作根据

FSC当前的状态输入带上的当前字符

栈顶符号进行状态改变和入栈或出栈操作将读头向右移动一个单元第9页，课件共166页，创作于2023年2月5.1.1确定的下推自动机

例5-1语言L={w|w∈(a,b)*，且a、b个数相等}

暂时不考虑状态

(或PDA仅有一个状态)第10页，课件共166页，创作于2023年2月初始栈为空从左到右逐个扫描串w∈(a，b)*第11页，课件共166页，创作于2023年2月入栈若栈为空,当前符号是a,则A入栈若栈为空,当前符号是b,则B入栈若栈顶为A,当前符号是a,则A入栈若栈顶为B,当前符号是b,则B入栈第12页，课件共166页，创作于2023年2月出栈若栈顶为A,当前符号是b，则A出栈若栈顶为B,当前符号是a，则B出栈第13页，课件共166页，创作于2023年2月若串w有相同个数的a和b当且仅当w扫描结束后，栈为空。第14页，课件共166页，创作于2023年2月注意PDA在两种情况下停机：串扫描结束没有对应的规则第15页，课件共166页，创作于2023年2月串扫描结束栈如果为空就接收扫描过的串。第16页，课件共166页，创作于2023年2月对于非正式的算法，用形式化的方式进行描述：第17页，课件共166页，创作于2023年2月特殊的符号Z0表示栈底初始化时先压入栈第18页，课件共166页，创作于2023年2月<x，D，V>规则(指令)若x是w的当前符号

D是栈顶符号则用符号串V代替D即将D弹出栈，而将串V压入栈第19页，课件共166页，创作于2023年2月具体若x是w的当前符号，栈顶符号为D<x，D，ε>将D弹出栈<x，D，AD>将A压入栈，成为新的栈顶第20页，课件共166页，创作于2023年2月一般地若x是w的当前符号，栈顶符号为D<x，D，A1A2…Ak>表示：将D弹出栈将串A1A2…Ak压入栈(A1为新栈顶)第21页，课件共166页，创作于2023年2月例5-1算法的形式化描述<a，Z0，AZ0><b，Z0，BZ0><a，A，AA><b，B，BB><a，B，ε><b，A，ε><ε，Z0，ε>第22页，课件共166页，创作于2023年2月规则<ε，Z0，ε>表示将w扫描结束后，将栈置成空也表示该PDA可以接收空串ε第23页，课件共166页，创作于2023年2月思考：如何接收语言L={w|w∈(a,b)+,且a和b个数相等}?第24页，课件共166页，创作于2023年2月例：语言L={anbn|n≥0}定义：<a，Z0，AZ0><a，A，AA><b，A，ε><ε，Z0，ε>第25页，课件共166页，创作于2023年2月则还可以接收语言{(ab)n|n≥0}，或{ambm(ab)n|m≥0,n≥0}等语言。第26页，课件共166页，创作于2023年2月思考：如何接收语言L={anbn|n>0}L={anbn|n≥0}L={(ab)n|n>0}L={(ab)n|n≥0}第27页，课件共166页，创作于2023年2月例5-2L={wcwT|w∈(a，b)*}识别语言第28页，课件共166页，创作于2023年2月思想：将w的各个字符压入栈后栈中的内容从栈顶到栈底的顺序刚好是wT的顺序第29页，课件共166页，创作于2023年2月为了区别压栈和出栈动作增加两个状态----read和match

PDA处于read状态时，处理整个串的前半部分，将对应的符号压入栈第30页，课件共166页，创作于2023年2月扫描到字母c时PDA的状态转为match开始处理整个串的后半部分，将栈中的内容出栈。第31页，课件共166页，创作于2023年2月规则<q，x，D，q′，V>

若PDA处于状态qw的当前字母是x当前栈顶符号为D则自动机的状态改变为q′并用符号串V代替D第32页，课件共166页，创作于2023年2月（在本例中）用Z代表任意的栈顶符号规则〈read，a，Z，read，AZ>可以表示以下3条规则：〈read，a，Z0，read，AZ0>〈read，a，A，read，AA>〈read，a，B，read，AB>第33页，课件共166页，创作于2023年2月用下列的规则来描述PDA〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，c，Z，match，Z>〈match，a，A，match，ε>〈match，b，B，match，ε>〈match，ε，Z0，match，ε>第34页，课件共166页，创作于2023年2月若串w是该语言的合法的串当且仅当w扫描结束后，栈为空。第35页，课件共166页，创作于2023年2月Z0符号栈串abbcbba的处理过程ABreadmatch=>B第36页，课件共166页，创作于2023年2月扫描到字母c栈内的内容（从栈顶到栈底）是扫描过的串的逆与未扫描过的串的顺序相同此时，不作出栈和入栈操作，仅仅把PDA的状态从read改变到match。第37页，课件共166页，创作于2023年2月接收语言L={anbn|n>0}〈q0，a，Z0，q0，AZ0>〈q0，a，A，q0，AA>〈q0，b，A，q1，ε>〈q1，b，A，q1，ε>〈q1，ε，Z0，q1，ε>第38页，课件共166页，创作于2023年2月5.1.2不确定的下推自动机例5-3语言L={wwT|w∈(a,b)*}第39页，课件共166页，创作于2023年2月

没有中心点字符在扫描过程中，就没有确定的位置进行状态的变换具有不确定性。第40页，课件共166页，创作于2023年2月使用规则〈read，ε，Z，match，Z>来代替〈read，c，Z，match，Z>即在read状态时，可随时改变为match状态（栈的内容和扫描符号不变）第41页，课件共166页，创作于2023年2月〈read，a，Z，read，AZ>〈read，b，Z，read，BZ>〈read，ε，Z，match，Z>〈match，a，A，match，ε>〈match，b，B，match，ε>〈match，ε，Z0，match，ε>第42页，课件共166页，创作于2023年2月该PDA是不确定的处于状态read状态时

随时都可以进行选择:继续扫描，或状态变换为match第43页，课件共166页，创作于2023年2月一个串w能够由PDA所识别：仅当串是wwT的形式且PDA状态在中心点进行了变换第44页，课件共166页，创作于2023年2月对于不确定的PDA和串w若存在至少一个可能的扫描过程使得当串w扫描结束时，栈为空则称串w能够被PDA所识别。第45页，课件共166页，创作于2023年2月接收语言L={(ab)n|n≥0}〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε〉第46页，课件共166页，创作于2023年2月接收语言L={(ab)n|n>0}〈q0，a，Z0，q0，AZ0>〈q0，b，A，q1，ε>〈q1，a，Z0，q2，AZ0>〈q2，b，A，q1，ε>〈q1，ε，Z0，q1，ε>第47页，课件共166页，创作于2023年2月定义5-1下推自动机PDA是一个七元式：M=(Q，∑，Г，δ，q0，Z0，F)

Q是一个有限状态的集合

∑是输入串的字母集合

Г是栈内符号集合第48页，课件共166页，创作于2023年2月q0∈Q是开始状态Z0∈Г是栈底符号FQ是接收状态集合第49页，课件共166页，创作于2023年2月δ：Q×(∑∪{ε})×Г→Q×Г*对于确定的PDA，有δ（q，x，D）=(q′，V)对于不确定的PDA，有(q′，V)∈δ（q，x，D）第50页，课件共166页，创作于2023年2月一般使用

<q，x，D，q′，V>表示δ函数第51页，课件共166页，创作于2023年2月定义5-2PDA格局(或瞬间描述ID)格局代表某个时刻PDA的情况PDA的格局是一个三元式(q，w，σ)其中，q为状态第52页，课件共166页，创作于2023年2月w=x1x2…xn还没有被扫描到的串(将扫描x1)σ=Z1Z2…Zm栈的内容(Z1在栈顶，Zm在栈底)第53页，课件共166页，创作于2023年2月PDA初始格局为(q0，w，Z0)接收格局为(q，ε，ε)其中:q∈Q（与接收状态无关）第54页，课件共166页，创作于2023年2月格局的转换是由于状态转换函数的作用引起的第55页，课件共166页，创作于2023年2月确定的PDA<q，x，A，q1，A1A2…Ak>引起的格局转换为：

(q，xw，Aσ)=>(q1，w，A1A2…Akσ)第56页，课件共166页，创作于2023年2月不确定的PDA（情况1）①<q，x，A，q1，A1A2…Ak>则(q,xw,Aσ)=>(q1，w,A1A2…Akσ)②<q，ε，A，q2，B1B2…Bj>则(q,xw,Aσ)=>(q2，xw，B1B2…Bjσ)第57页，课件共166页，创作于2023年2月不确定的PDA（情况2）①<q，x，A，q1，A1A2…Ak>则(q,xw,Aσ)=>(q1，w，A1A2…Akσ)②<q，x，A，q2，B1B2…Bj>则(q,xw,Aσ)=>(q2，w，B1B2…Bjσ)第58页，课件共166页，创作于2023年2月用=>*代表格局的任意次变换第59页，课件共166页，创作于2023年2月不确定PDA对于某一格局可能会有不同的下一格局。第60页，课件共166页，创作于2023年2月5.1.3PDA接收语言的两种方式定义5-3PAD以空栈方式接收的语言为L(M），且L(M)={w|(q0，w，Z0)=>*(q,ε,ε)

q∈Q}第61页，课件共166页，创作于2023年2月接收格局与接收状态无关只要当串w扫描结束，而栈为空则串w被PDA以空栈方式所接收。第62页，课件共166页，创作于2023年2月定义5-4PAD以终态方式接收的语言为F(M)，且F(M)={w|(q0,w，Z0)=>*(q′,ε,σ)q′∈F,σ∈Г*}

第63页，课件共166页，创作于2023年2月接收格局与栈是否为空无关只要当串w扫描结束，而PDA处于某个接收状态则串w被PDA以终态方式所接收。第64页，课件共166页，创作于2023年2月定理5-1语言L被PDA以终态方式所接收当且仅当

它被PDA以空栈方式所接收。即终态接收与空栈接收方式等价。第65页，课件共166页，创作于2023年2月证明：略第66页，课件共166页，创作于2023年2月5.1.4广义PDA和单态PDA定义5-5广义的PDA是七元式

PDA=(Q,∑，Г，δ，q0，Z0，F)（除了δ外，其余同一般的PDA）其中第67页，课件共166页，创作于2023年2月Q是一个有限状态的集合∑是输入串的字母集合Г是栈内符号集合q0∈Q是开始状态Z0∈Г是初始的栈底符号FQ是接收状态(终止状态)集合第68页，课件共166页，创作于2023年2月δ：Q×(∑∪{ε})×Г+→Q×Г*(q，x，B1B2…Bk)=(q′，C1C2…Cn)一般形式为<q，x,B1B2…Bk，q′，C1C2…Cn>第69页，课件共166页，创作于2023年2月一般的PDA，栈顶只是一个符号广义PDA的栈顶可以为多个符号。第70页，课件共166页，创作于2023年2月定理5-4若语言L能由广义PDA所接收则L能够由一般的PDA所接收。第71页，课件共166页，创作于2023年2月证明思路

广义的PDA的一条规则一般PDA的多条规则的组合就是第72页，课件共166页，创作于2023年2月证明：对于广义的PDA的任意一条规则<q,x,B1B2…Bk，q′，C1C2…Cn>增加状态r1，r2，…，rk-1，第73页，课件共166页，创作于2023年2月<q，x，B1B2…Bk，q′，C1C2…Cn>改造为：

<q，x，B1，r1，ε><r1，ε，B2，r2，ε>…<rk-1，ε，Bk，q′，C1C2…Cn

>第74页，课件共166页，创作于2023年2月得到一般的PDA′且L=L(PDA′)。第75页，课件共166页，创作于2023年2月定义5-6单态PDA

仅有一个状态的PDA

规则简化为<x，D，V>第76页，课件共166页，创作于2023年2月(等价性)问题一个NFA是否可以转换为一个单态PDA？第77页，课件共166页，创作于2023年2月思路NFA=（Q，∑,δ，q0，F）将NFA的状态当作PDA的栈内符号构造单态的PDA

=（{*}，∑，Q，δ′，*，q0，{*})第78页，课件共166页，创作于2023年2月NFA：δ(q，x)={q1，q2，…

qn｝单态的PDA：

<x，q，q1

><x，q，q2

>…<x，q，qn

>第79页，课件共166页，创作于2023年2月NFA：若q∈δ*(q0，w)单态的PDA：有（*，w，q0）=>*（*，ε，q）第80页，课件共166页，创作于2023年2月NFA：若δ(q，x)∩F≠ф

单态的PDA：<x

，q

，ε

>第81页，课件共166页，创作于2023年2月因此NFA：

δ*(q0，w)∩F≠ф单态的PDA：（*，w，q0）=>*（*，ε，ε）即L(NFA)=L(PDA)第82页，课件共166页，创作于2023年2月右线性文法G=（∑，V，S，P）也可以对应一个单态的PDA，第83页，课件共166页，创作于2023年2月产生式

A→bB

A→b

PDA的规则<b，A，B>

<b，A，ε>第84页，课件共166页，创作于2023年2月将文法的开始符号S当作是单态PDA的栈底符号，则第85页，课件共166页，创作于2023年2月对于文法GS=>*w1A=>w1bB=>*w1bw2=w对于单态PDA(*，w1bw2，S)=>*(*，bw2，A)=>(*，w2，B)=>*(*，ε，ε)第86页，课件共166页，创作于2023年2月例5-4语言L={anbn|n≥1}文法S→aSBS→aBB→b<a，S，SB><a，S，B><b，B，ε>单态PDA第87页，课件共166页，创作于2023年2月对于串anbn，单态的PDA可能会有以下的格局转换：①(*，anbn，S）=>n(*，an-jbn，SBj）②(*，anbn，S）=>n（*，an-kbn，Bk）③(*，anbn，S）=>n（*，bn，Bn）其中：①是导出②和③的中间过程；第88页，课件共166页，创作于2023年2月②会导致停机，因为没有合适的规则<a，B，？>③可以完成最后的转换：（*，bn，Bn）=>*（*，ε，ε）第89页，课件共166页，创作于2023年2月使用n-1次规则<a，S，SB>

1次规则<a，S，B>n次规则<b，B，ε>第90页，课件共166页，创作于2023年2月5.1.5下推自动机的存储技术参考Turing的存储技术。略第91页，课件共166页，创作于2023年2月5.1.6PDA扫描多个符号参考Turing的扫描多个符号技术。略第92页，课件共166页，创作于2023年2月5.2上下文无关文法和范式范式是指标准的形式在代数中，2/4，3/6，…的范式是1/2。本节讨论在上下文无关文法的几个重要的范式。第93页，课件共166页，创作于2023年2月定理5-5G是一个上下文无关文法，则存在一个上下文无关文法G′，使得：①L(G)=L(G′)②若ε≠L(G)，则G′没有空串产生式第94页，课件共166页，创作于2023年2月③若ε∈L(G)，则G′有S′→ε，且S′不出现在G′的任何产生式的右边④G′中没有A→B形式的产生式。第95页，课件共166页，创作于2023年2月证明前3点是空串定理的内容(见2.6)第4点证明参见参考文献1。第96页，课件共166页，创作于2023年2月5.2.1Chomsky范式(CNF)定义5-7上下文无关文法G=(∑，V，S，P)若G的每个产生式是下列形式之一：第97页，课件共166页，创作于2023年2月

A→BCA，B，C∈V

A→a

A∈V，a∈∑

S→ε且S不出现在产生式的右边则G是Chomsky范式(CNF)。第98页，课件共166页，创作于2023年2月定理5-6G是一个上下文无关文法，则存在一个等价的上下文无关文法G′使得L(G)=L(G′)，且G′是CNF。第99页，课件共166页，创作于2023年2月证明对于任意的上下文无关文法G首先使它满足定理5-5的要求对于文法中的任意的产生式A→B1B2…Bm

第100页，课件共166页，创作于2023年2月假设每个Bi都是非终结符

(若不是，则使用非终结符Bi′来代替Bi，并增加产生式Bi′→Bi)

第101页，课件共166页，创作于2023年2月A→B1B2…Bm若m=2，满足了CNF要求；m≥3，将它改造为m-1个产生式：第102页，课件共166页，创作于2023年2月A→B1B2…Bm

A→B1C1 C1→B2C2…Cm-3→Bm-2Cm-2 Cm-2→Bm-1Bm第103页，课件共166页，创作于2023年2月其中C1，C2，…，Cm-2是新加的非终结符得到的文法G′是CNF且L(G)=L(G′)。证毕。第104页，课件共166页，创作于2023年2月5.2.2Greibach范式(GNF)定义5-8上下文无关文法G=(∑，V，S，P)是GNF，若G的每个产生式形式为A→bWb∈∑，W∈V*第105页，课件共166页，创作于2023年2月定理5-7G是一个上下文无关文法，则存在一个等价的上下文无关文法G′，使得L(G)=L(G′)且G′中没有直接左递归的产生式，即不存在A→Av形式的产生式其中：A∈V，v∈(∑UV)+。第106页，课件共166页，创作于2023年2月没有直接左递归的文法也称为无直接左递归范式（NLR）。第107页，课件共166页，创作于2023年2月证明见2.7。第108页，课件共166页，创作于2023年2月某些文法可能没有直接左递归，但可能会有间接左递归。第109页，课件共166页，创作于2023年2月定理5-8G是一个上下文无关文法，则存在一个等价的上下文无关文法G′，使得L(G)=L(G′)且G′中没有间接左递归的产生式。第110页，课件共166页，创作于2023年2月没有间接左递归的文法也称为无间接左递归范式。第111页，课件共166页，创作于2023年2月证明见2.7。第112页，课件共166页，创作于2023年2月定理5-9G是任意一个上下文无关文法，则存在一个等价的上下文无关文法G′，使得L(G)=L(G′)且G′是Greibach范式(GNF)。第113页，课件共166页，创作于2023年2月对于任意的上下文无关文法G，产生式形式为Ai→AjwAi→aw或第114页，课件共166页，创作于2023年2月假设w包含的字符全为非终结符对于Ai→aw，本身就是GNF的形式第115页，课件共166页，创作于2023年2月对于Ai→Ajw

利用消除左递归的算法，在消除左递归的以后，从An-1开始，将An代入到An-1，将An-1代入到An-2，直至A1，再将增加的非终结符的产生式的开头符号代替掉，得到GNF。第116页，课件共166页，创作于2023年2月5.3PDA与上下文无关语言PDA识别的语言是上下文无关语言。第117页，课件共166页，创作于2023年2月定理5-10对于上下文无关语言L和文法G若L=L(G)，则语言L能被(广义)不确定的PDA所接收第118页，课件共166页，创作于2023年2月证明：假设文法是GNF范式构造一个单态的PDA来接收语言L；第119页，课件共166页，创作于2023年2月文法G中有3种形式的产生式，它们分别对应PDA的规则：

S→ε

A→bA→bW其中：A∈V，W∈V+，<ε，S，ε><b，A，ε><b，A，W>第120页，课件共166页，创作于2023年2月需要证明语言L=L(PDA)。为证明之，先证明（*，w1w2，S）=>*（*，w2，σ）iffS=>*w1σ第121页，课件共166页，创作于2023年2月即扫描串后w1，M栈内符号串为σ；若上述成立，假设w2=σ=ε，则（*，w1，S）=>*（*，ε，ε）

iffS=>*w1第122页，课件共166页，创作于2023年2月现在用归纳法证明（对串w1的长度进行归纳）（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ第123页，课件共166页，创作于2023年2月证明基础：当w1=ε，有两种情况：a）（*，w2，S）=>*（*，w2，S）

iffS=>*S是成立的；b）若S→ε在G中，则有（*,w2，S）=>*（*，w2，ε）

iffS=>*ε是成立的；第124页，课件共166页，创作于2023年2月假设：当w1≠ε时，长度为n时；（*,w1w2，S）=>*（*,w2，σ）iffS=>*w1σ令σ=Aг，w2=aw3，（将w1a当作新的w1，长度为n+1），则第125页，课件共166页，创作于2023年2月(*,w1aw3，S）=>*（*,aw3，Aг）

iffS=>*w1Aг而（*，aw3，Aг）=>（*，w3，г′г）iffA→aг′第126页，课件共166页，创作于2023年2月因此(*，w1aw3，S)=>*(*，w3，г′г)

iffS=>*w1aг′г所以：假设成立，证毕。第127页，课件共166页，创作于2023年2月例5-10文法G为

S→(L|εL→(LL|)对于串：(()())第128页，课件共166页，创作于2023年2月构造的单态的PDA（栈底为S）为：<(，S，L><ε，S，ε><(，L，LL><)，L，ε>S→(LS→εL→(LLL→)第129页，课件共166页，创作于2023年2月对于单态的PDA可以构造对应的上下文无关文法G使得L(M)=L(G)第130页，课件共166页，创作于2023年2月例5-11有单态的PDA：<a，Z0，AZ0><b，Z0，BZ0><a，A，AA><b，B，BB><a，B，ε><b，A，ε><ε，Z0，ε>第131页，课件共166页，创作于2023年2月构造上下文无关文法G（用Z代替Z0作为开始符号）为：Z→aAZ|bBZ|εA→aAA|bB→bBB|a第132页，课件共166页，创作于2023年2月例5-12构造PDA接收语言L={w2wT|w∈{0,1}*}第133页，课件共166页，创作于2023年2月解法1：read--match第134页，课件共166页，创作于2023年2月解法2：GNF=>PDA产生L的上下文无关文法：S→2|0S0|1S1第135页，课件共166页，创作于2023年2月将文法转化成GNF

S→2|0SA|1SBA→0B→1第136页，课件共166页，创作于2023年2月构造单态PDA<0，S，SA>//S→0SA<1，S，SB>//S→1SB<2，S，ε>//S→2<0，A，ε>//A→0<1，B，ε>//B→1第137页，课件共166页，创作于2023年2月定理5-11对于单态的PDA存在一个上下文无关文法G使得L（G）=L(PDA)且G为GNF范式形式。第138页，课件共166页，创作于2023年2月证明PDA文法<a，B，σ>B→aσ<a，B，ε>B→a

第139页，课件共166页，创作于2023年2月根据单态的PDA可以得到对应的GNF。而多态的PDA，不可以直接得到GNF。第140页，课件共166页，创作于2023年2月问题多态PDA如何得到对应的上下文无关文法？第141页，课件共166页，创作于2023年2月定理5-12对于多态PDA，存在上下文无关文法G，使得L(G)=L(M)。第142页，课件共166页，创作于2023年2月证明构造上下文无关文法G思路为用文法的一个推导模拟PDA的一个动作。具体过程参考P135。第143页，课件共166页，创作于2023年2月对于多态PDA得到对应的上下文无关文法的产生式具有如下的形式：

A→aA1A2…AnA→A1A2…AnA→aA→ε第144页，课件共166页，创作于2023年2月定理5-13若M是多态的PDA，则存在一个单态PDA′，使得L(PDA)=L(PDA′)第145页，课件共166页，创作于2023年2月证明略。第146页，课件共166页，创作于2023年2月总之对于一个PDA存在一个上下文无关文法G，使得L(M)=L(G)。第147页，课件共166页，创作于2023年2月注意确定PDA和不确定PDA不等价。第148页，课件共166页，创作于2023年2月例构造PDA接收语言L={w|w∈{a,b}*

w中a的个数为b的2倍且a必须成对出现}第149页，课件共166页，创作于2023年2月思路：将一个a当作一个成对的aa:构造上下文无关文法G为：Z→aCAZ|bBZ|εA→aCAA|bB→