TransWikia.com

Lengths of "all-accepted" words in Context Free languages

Theoretical Computer Science Asked by Marzio De Biasi on October 30, 2021

If $L$ is a Context Free language, it can happen that for some $n$, all words of length $n$ are in $L$. If we consider the
set $A_L$ of such lengths represented in unary, we may guess that such set is Context Free (and hence regular), but it is not the case.

More formally; if $L in CF$ define:

$A_L = { 1^n mid |w|=n Rightarrow w in L }$

There are CF languages for which $A_L notin REG$.

The example I have in mind uses the sequence of tape configurations (alternating straight/reverse order like in the proof of the undecidability of $L = Sigma^*$) of a valid Turing machine computation that on input $x$ (in binary), writes $1^x$ on the tape and halts.

Before spending more time in formalizing it, I wonder if there is a simpler example, or if I can find it in some books/papers (I made some searches but probably I’m using the wrong terms).

One Answer

The shortest word in $A_L$ is not bounded by a recursive function in the size of a given context-free grammar describing $L$. See here for more results in that direction: https://doi.org/10.4230/LIPIcs.STACS.2020.16

Answered by Hermann Gruber on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP