请输入您要查询的字词:

 

单词 LeftmostDerivation
释义

leftmost derivation


Let G=(Σ,N,P,σ) be a context-free grammar. Recall that a word v is generated by G if it is

  • a word over the set T:=Σ-N of terminals, and

  • derivablePlanetmathPlanetmath from the starting symbol σ.

The second condition simply says that there is a finite sequencePlanetmathPlanetmath of derivation steps, starting from σ, and ending at v:

σ=v0v1vn=v

For each derivation step vivi+1, there is a production Xw in P such that

vi=aXb,
vi+1=awb.

Note that X is a non-terminal (an element of N), and a,b,w are words over Σ.

Definition. Using the notations above, if X is the leftmost non-terminal occurring in vi, then we say the derivation step vivi+1 is leftmost. Dually, vivi+1 is rightmost if X is the rightmost non-terminal occurring in vi.

Equivalently, vivi+1 is leftmost (or rightmost) if a (or b) is a word over T.

A derivation is said to be leftmost (or rightmost) if each of its derivation steps is leftmost (or rightmost).

Example. Let G be the grammar consisting of a,b as terminals, σ,X,Y,Z as non-terminals (with σ as the starting symbol), and σXY, Xa, Yb, σZY, and ZXσ as productions. G is clearly context-free.

The word a2b2=aabb can be generated by G by the following three derivations:

  1. 1.

    σZYXσYXXYYXaYYXaYbXabbaabb,

  2. 2.

    σZYXσYaσYaXYYaaYYaabYaabb,

  3. 3.

    σZYZbXσbXXYbXXbbXabbaabb.

The second is leftmost, the third is rightmost, and the first is neither.

Note that in every derivation, the first and last derivation steps are always leftmost and rightmost.

Remarks.

  • One of the main properties of a context-free grammar G is that every word generated by G is derivable by a leftmost (correspondingly rightmost) derivation, which can be used to show that for every context-free language L, there is a pushdown automaton accepting every word in L, and conversely that the set of words accepted by a pushdown automaton is context-free.

  • Leftmost derivations may be defined for any arbitrary formal grammar G satisfying the condition

    (*) no terminal symbols occur on the left side of any production.

    Given two words u,v, we define uLv if there is a production AB such that u=xAy and v=xBy such that x is a terminal word. By taking the reflexive transitive closure of L, we have the leftmost derivation L*. It can be shown that for any grammar G satisfying condition (*), the languagePlanetmathPlanetmath LL(G) consisting of terminal words generated by G via leftmost derivations is always context-free.

References

  • 1 S. Ginsburg The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York (1966).
  • 2 D. C. Kozen Automata and Computability, Springer, New York (1997).

随便看

 

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

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/4 8:51:56