Is there a prefix-free regular language whose set of proper prefixes is not regular

708 Views Asked by At

Is there a regular language $L$ such that the language $$L^\prime := \{ w : w\text{ is a proper prefix of a word in }L \}$$ has the following properties:

  1. $L^\prime$ is not regular, and
  2. $L^\prime$ and $L$ have no words in common.
1

There are 1 best solutions below

0
On BEST ANSWER

Such a regular language does not exist, and it is because of the following: Given any regular language $L$, the language $L^\prime$ consisting of all proper prefixes of words in $L$ is regular.

Let $L$ be a regular language, and fix a DFA $D = ( Q , \Sigma , \delta , q_0 , F )$ accepting it. Consider the DFA $D^\prime = ( Q , \Sigma , \delta , q_0 , F^\prime )$, where $F^\prime$ consists of all states in $Q$ from which an accepting state of $D$ (i.e., a state in $F$) is reachable by a nonempty word. It is not too difficult to show that $D^\prime$ accepts $L^\prime$, and so $L^\prime$ is regular.