A DIRECT PROOF OF INHERENT AMBIGUITY OF A SIMPLE CONTEXT-FREE LANGUAGE

被引：9

作者：

MAURER, HA

机构：

[1] University of Calgary, Department of Mathematics, Calgary, Alberta, Canada

来源：

JOURNAL OF THE ACM | 1969年 / 16卷 / 02期

关键词：

D O I：

10.1145/321510.321517

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A direct and self-contained proof is given of the inherent ambiguity of the context-free language L = {aibici ∣ i,j > 1} ∪ {aibici ∣ i,j > 1}, which is the solution to an open problem pointed out by Ginsburg. © 1969, ACM. All rights reserved.

引用

页码：256 / &

共 7 条

[1]

Chomsky N., 1958, INFORM CONTR, V1, P91, DOI DOI 10.1016/S0019-9958(58)90082-2

[2]

CHOMSKY N, 1963, HDB MATHEMATICAL PSY, P324

[3] BOUNDED ALGOL-LIKE LANGUAGES [J].

GINSBURG, S ;

SPANIER, EH .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1964, 113 (02) :333-+

[4] AMBIGUITY IN CONTEXT FREE LANGUAGES [J].

GINSBURG, S ;

ULLIAN, J .

JOURNAL OF THE ACM, 1966, 13 (01) :62-+

[5]

GINSBURG S, 1966, MATHEMATICAL THEORY

[6] ON CONTEXT-FREE LANGUAGES [J].

PARIKH, RJ .

JOURNAL OF THE ACM, 1966, 13 (04) :570-+

[7]

PARIKH RJ, 1961, 60 MIT RES LAB EL QU, P199

← 1 →