A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
From MaRDI portal
Publication:5507987
DOI10.1145/321250.321254zbMath0135.18404OpenAlexW2010117085WikidataQ56092148 ScholiaQ56092148MaRDI QIDQ5507987
Publication date: 1965
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321250.321254
Related Items
The theory of languages, Context-free graph languages of bounded degree are generated by apex graph grammars, Greibach normal form transformation, revisited, Normal Forms for Multiple Context-Free Languages and Displacement Lambek Grammars, A descriptive characterisation of linear languages, The theory of languages, Recursive descent parsing for Boolean grammars, A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free, A note on left-recursive rules and the partitioning of a recognition matrix for syntax-directed translation, Gaifman's theorem on categorial grammars revisited, Greibach normal form for \(\omega\)-algebraic systems and weighted simple \(\omega\)-pushdown automata, A computation model with automatic functions and relations as primitive operations, A method for transforming grammars into LL(k) form, Conjunctive and Boolean grammars: the true general case of the context-free grammars, One-Way Restarting Automata and Their Sensitivitys, On translating context-free grammars into Lambek grammars, A survey on automata with translucent letters, Stochastic grammars and languages, Knapsack in graph groups, A pumping lemma for flip-pushdown languages, Generalizing input-driven languages: theoretical and practical benefits, Position-restricted grammar forms and grammars, Identification in the Limit of k,l-Substitutable Context-Free Languages, On LLP(k) grammars and languages, Immunity and pseudorandomness of context-free languages, Hardest languages for conjunctive and Boolean grammars, Extended Lambek Calculi and First-Order Linear Logic, Characterization of context-free languages, An elementary proof of double Greibach normal form, The Hardest Language for Conjunctive Grammars, Simple Matrix Grammars and Their Leftmost Variants, Conjunctive grammars with restricted disjunction, Transductions des langages de Chomsky, Algebraically complete semirings and Greibach normal form, Model checking propositional dynamic logic with all extras, On the pre-AFL of \([lg\;n\) space and related families of languages], Conjunctive Grammars with Restricted Disjunction, An elementary proof of a generalization of double Greibach normal form, Normal forms of deterministic grammars, Control sets on context-free grammar forms, Normal form algorithms for extended context-free grammars, The multiplicative-additive Lambek calculus with subexponential and bracket modalities, A Greibach normal form for context-free graph grammars, String Analysis as an Abstract Interpretation, On equivalence of grammars through transformation trees, Monadic recursion schemes: The effect of constants, Generating context-free languages using spiking neural P systems with structural plasticity, Properties of syntax directed translations, Deontology of compound actions, Principal AFL, Time-bounded grammars and their languages, On stochastic context-free languages, Substitution expressions, A homomorphism theorem for weighted context-free grammars, SOME DECISION QUESTIONS CONCERNING THE TIME COMPLEXITY OF LANGUAGE ACCEPTORS, Constructing a realtime deterministic pushdown automaton from a grammar, Double Greibach operator grammars, Greibach normal form transformation revisited., Restrictions on NLC graph grammars, Categorial dependency grammars, COMPLEXITY OF THE INFINITARY LAMBEK CALCULUS WITH KLEENE STAR, Control sets on grammars
