请输入您要查询的字词:

 

单词 GreibachNormalForm
释义

Greibach normal form


A formal grammar G=(Σ,N,P,σ) is said to be in Greibach normal form if every production has the following form:

AaW

where AN (a non-terminal symbol), aΣ (a terminal symbol), and WN* (a word over N).

A formal grammar in Greibach normal form is a context-free grammar. Moreover, any context-free language not containing the empty word λ can be generated by a grammar in Greibach normal form. And if a context-free language L contains λ, then L can be generated by a grammar that is in Greibach normal form, with the additionPlanetmathPlanetmath of the production σλ.

Let L be a context-free language not containing λ, and let G=(Σ,N,P,σ) be a grammar in Greibach normal form generating L. We construct a PDA M from G based on the following specifications:

  1. 1.

    M has one state p,

  2. 2.

    the input alphabet of M is Σ,

  3. 3.

    the stack alphabet of M is N,

  4. 4.

    the initial stack symbol of M is the start symbol σ of G,

  5. 5.

    the start state of M is the only state of M, namely p

  6. 6.

    there are no final states,

  7. 7.

    the transition function T of M takes (p,a,A) to the singleton {(p,W)}, provided that AaW is a production of G. Otherwise, T(p,a,A)=.

It can be shown that L=L(M), the languagePlanetmathPlanetmath accepted on empty stack, by M. If we further define T(p,λ,σ):={(p,λ)}, then M accepts L{λ}. As a result, any context-free language is accepted by some PDA.

References

  • 1 J.E. Hopcroft, J.D. Ullman, Formal Languages and Their RelationMathworldPlanetmath to Automata, Addison-Wesley, (1969).
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 21:12:31