Most Pseudo-copy Languages Are Not Context-Free

Hyunjoon Cheon, Joonghyuk Hahn, Yo Sub Han, Sang Ki Ko

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations


It is well known that the copy language L= { ww∣ w∈ Σ} is not context-free despite its simplicity. We study pseudo-copy languages that are defined to be sets of catenations of two similar strings, and prove non-context-freeness of these languages. We consider the Hamming distance and the edit-distance for the error measure of the two similar strings in pseudo-copy languages. When the error has an upper bound or a fixed value, we show that the pseudo-copy languages are not context-free. Similarly, if the error has a lower bound of at least four, then such languages are not context-free, either. Finally, we prove that all these pseudo-copy languages are context-sensitive.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings
EditorsChi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages12
ISBN (Print)9783030895426
StatePublished - 2021
Event27th International Conference on Computing and Combinatorics, COCOON 2021 - Tainan, Taiwan, Province of China
Duration: 24 Oct 202126 Oct 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13025 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Computing and Combinatorics, COCOON 2021
Country/TerritoryTaiwan, Province of China


  • Context-freeness
  • Edit-distance
  • Hamming distance
  • Pseudo-copy languages


Dive into the research topics of 'Most Pseudo-copy Languages Are Not Context-Free'. Together they form a unique fingerprint.

Cite this