A New Normal-Form Theorem for Context-Free Phrase Structure Grammars

Journal of the ACM - Tập 12 Số 1 - Trang 42-52 - 1965
Sheila A. Greibach1
1Harvard University, Cambridge, Massachusetts

Tóm tắt

Từ khóa


Tài liệu tham khảo

CHOSXY , N. Formal properties of grammars . In Hardboo qf fathe;naica{ PqcJmL ogy, voL II . Lute, R. D., Bush, R. R., and Galanter, E. (Eds.), Wiley New York , 1963 . CHOSXY, N. Formal properties of grammars. In Hardboo qf fathe;naica{ PqcJmL ogy, voL II. Lute, R. D., Bush, R. R., and Galanter, E. (Eds.), Wiley New York, 1963.

EVEY , J. The Theory and Applications of Pushdown Store Mtchines. Doct. Thesis , Harvard U. , Cambridge , Mass ., 1963 . EVEY, J. The Theory and Applications of Pushdown Store Mtchines. Doct. Thesis, Harvard U., Cambridge, Mass., 1963.

10.1145/366663.366704

10.1145/368310.368385

KUNO , S , axu 0TTINOER , A. G. Multiple-path syntactic analyzer. In informaffon Processing 62 , C. M. Popplewell (Ed.), North Holland , Amsterdam , 1962 -1963. KUNO, S, axu 0TTINOER, A. G. Multiple-path syntactic analyzer. In informaffon Processing 62, C. M. Popplewell (Ed.), North Holland, Amsterdam, 1962-1963.

YNQ v, V. A model and hypothesis for language structure . Proc. Miner. Ptil. Soc. i07 , 5 ( Oct. 1960 ). YNQv, V. A model and hypothesis for language structure. Proc. Miner. Ptil. Soc. i07, 5 (Oct. 1960).

CHOMSKY , N , _NrD SCHU rZEXBE RGER , M. P. The algebraic theory of context-free languages . In Computer Programming and Formal Sytems, Braffort, P., and Hirschberg, I9. (Eds.) , North Holland , Amsterdam , 1963 . CHOMSKY, N, _NrD SCHUrZEXBERGER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Sytems, Braffort, P., and Hirschberg, I9. (Eds.), North Holland, Amsterdam, 1963.

BHILLEL , Y. , PE a LES , M., YD SI txe, E . On formal properties of simple phrase structure grammars. Zeit. Phonet. Sprachwis. Komm,wnih . Forsch. 1 , 2 ( 1961 ). BHILLEL, Y., PEaLES, M., YD SItxe, E. On formal properties of simple phrase structure grammars. Zeit. Phonet. Sprachwis. Komm,wnih. Forsch. 1, 2 (1961).

Kuo S. Automatic transformation of au admissible PSG into a standard form PSG. Unpublished paper. Kuo S. Automatic transformation of au admissible PSG into a standard form PSG. Unpublished paper.

FENICHL R. Private communication. FENICHL R. Private communication.

Ra BIN , M. O. anD SCOTT , D . Finite automata and their decision problems. IBM Y. ReS , Develop. 8 ( 1959 ), 114 - 125 . RaBIN, M. O. anD SCOTT, D. Finite automata and their decision problems. IBM Y. ReS, Develop. 8 (1959), 114-125.

HAY s, D. G. Grouping and dependercy theories. Paper P-l010 , RAND Corp., SANta Moniea Calif ,, 1960 . HAYs, D. G. Grouping and dependercy theories. Paper P-l010, RAND Corp., SANta Moniea Calif,, 1960.

GAIFMAN , M. Dependency systems and phrase structure systems. Paper P-2315 , RAND Corp., Santa Monica, Calif ., 1961 . GAIFMAN, M. Dependency systems and phrase structure systems. Paper P-2315, RAND Corp., Santa Monica, Calif., 1961.

10.1145/321172.321179

SPIELMAN J Operator and precedence frammars. Unpublished paper. SPIELMAN J Operator and precedence frammars. Unpublished paper.

ZIELLER C. A theorem of N. Chomsky and M. P. Schiitzenberger. Unpublished paper. ZIELLER C. A theorem of N. Chomsky and M. P. Schiitzenberger. Unpublished paper.

GIEIA c S. Inverses of phrase strueture generators. Doct. Thesis , Harvard U. Cambridge , Mass ., 1963 . GIEIAc S. Inverses of phrase strueture generators. Doct. Thesis, Harvard U. Cambridge, Mass., 1963.

10.1145/321127.321132

COMSY , N. Context-free grammars and pushdown storage. RLE Quart. Prog. Rep. No. 65 , M.t.T. , Cambridge , Mass ., Mar. 1962 . COMSY, N. Context-free grammars and pushdown storage. RLE Quart. Prog. Rep. No. 65, M.t.T., Cambridge, Mass., Mar. 1962.

McNAuGITON It. NU YAMADA H. Regular expressions and state graphs for auto mata fief Trans. C-9 (1960) 39-47. McNAuGITON It. NU YAMADA H. Regular expressions and state graphs for auto mata fief Trans. C-9 (1960) 39-47.