2

Along the same lines as what was asked in this post: Is there a simple characterization of regular languages closed under circular shifts?

Are there simple characterizations/properties of Context Free languages that are closed under circular shifts? ($xy \in L \Leftrightarrow yx \in L$)

A simple characterization could be:

  • put the grammar $G$ in Greibach Normal form

  • if $P_i \equiv S_i \to a_i \,X_{i_1}...X_{i_n}$ are the productions from the start symbol $S$

  • then $L$ is closed under circular shift if and only if

$L = L(G) \cap L(G')$

where $G'$ is obtained from $G$ replacing each production $P_i$ from the start symbol with:

$S'_i \to X_{i_1}...X_{i_n} \, a_i$

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127

0 Answers0