“pumping lemmas”的概念、定义、翻译、参考文献-科学参考

pumping lemmas

Computer

单词	pumping lemmas
释义	pumping lemmas Computer Two theorems in formal language theory that express necessary conditions for languages to be regular or context-free: If language L is regular, there exists an integer n such that, for any word z in L, \| z \|>n, there exist u,v,w with $z = u v w, v nonempty, \| v w \| \leq n,$ such that: $u v^{k} W \in L, for all k \geq 0$ If language L is context-free, there exist integers p and q such that, for any z in L, with \| z \|>p, there exist u,v,w,x,y with $\begin{array}{l} z = u v w x y, v and x nonempty, \\ \| v w x \| \leq q, \end{array}$ such that: $u v^{k} {wx}^{k} y \in L, for all k \geq 0$ The conditions are used in constructing algorithms for decision problems about regular and context-free grammars, and in proving certain languages are not regular or are not context-free.
随便看	pragmatic contradiction pragmaticism pragmatics Pragmatic Sanction pragmatic theory of truth pragmatism Prague, Defenestration of (1618) prairie prairie dog praise and blame pramana Prandtl, Ludwig (1875–1953) Prandtl number Prandtl’s one-seventh power law Prasad, Rajendra (1884–1963) praseodymium Pratt, John Henry Pratt, John Henry (?1811–1871) Pratt model prawn praxeology praxis prayer PRE pre-