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).
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP