A note on the sufficiency of Sokolowski's criterion for context-free languages

Anton Nijholt

doi:10.1016/0020-0190(82)90016-3

A note on the sufficiency of Sokolowski's criterion for context-free languages

Anton Nijholt

Research output: Contribution to journal › Article › Academic › peer-review

4 Citations (Scopus)

116 Downloads (Pure)

Abstract

Sokolowski's criterion is a condition on languages which can be used to show that a language is not context-free. The question has been raised whether the criterion is not only a necessary, but also a sufficient one. In this paper we show that the answer is negative.

Original language	Undefined
Pages (from-to)	207-207
Number of pages	1
Journal	Information processing letters
Volume	14
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(82)90016-3
Publication status	Published - 23 Jul 1982

Keywords

IR-66948
EWI-9266
HMI-SLT: Speech and Language Technology

Access to Document

10.1016/0020-0190(82)90016-3

ipl-1_1982Final published version, 108 KB

Cite this

@article{56d21d97f1cb4023a04e1b7f33783291,

title = "A note on the sufficiency of Sokolowski's criterion for context-free languages",

abstract = "Sokolowski's criterion is a condition on languages which can be used to show that a language is not context-free. The question has been raised whether the criterion is not only a necessary, but also a sufficient one. In this paper we show that the answer is negative.",

keywords = "IR-66948, EWI-9266, HMI-SLT: Speech and Language Technology",

author = "Anton Nijholt",

year = "1982",

month = jul,

day = "23",

doi = "10.1016/0020-0190(82)90016-3",

language = "Undefined",

volume = "14",

pages = "207--207",

journal = "Information processing letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - A note on the sufficiency of Sokolowski's criterion for context-free languages

AU - Nijholt, Anton

PY - 1982/7/23

Y1 - 1982/7/23

N2 - Sokolowski's criterion is a condition on languages which can be used to show that a language is not context-free. The question has been raised whether the criterion is not only a necessary, but also a sufficient one. In this paper we show that the answer is negative.

AB - Sokolowski's criterion is a condition on languages which can be used to show that a language is not context-free. The question has been raised whether the criterion is not only a necessary, but also a sufficient one. In this paper we show that the answer is negative.

KW - IR-66948

KW - EWI-9266

KW - HMI-SLT: Speech and Language Technology

U2 - 10.1016/0020-0190(82)90016-3

DO - 10.1016/0020-0190(82)90016-3

M3 - Article

VL - 14

SP - 207

EP - 207

JO - Information processing letters

JF - Information processing letters

SN - 0020-0190

IS - 5

ER -