2
$\begingroup$

I'm interested if the following language construction was studied. Let $\Sigma$ be an alphabet and $\Sigma^*$ is the set of all words over $\Sigma$. Consider a directed graph $G=\langle\Sigma^*,E\rangle$ together with a subset $S\subseteq\Sigma^*$ of its vertices. Now, define the language $L=\langle\Sigma,E,S\rangle$ consisting of all words reachable from $S$ in $G$. That is if $w\in L$ then $w\in S$ or there is a word $u\in S$ and some path from $u$ to $w$ in $G$. Can we describe $L$ using the Chomsky hierarchy?

$\endgroup$
1
$\begingroup$

No, you can obtain any submonoid $M$ of $\Sigma^*$ using your construction. Just take $S = \{1\}$ and $E = \{(x, xy) \mid x, y \in M\}$. Then $L = M$.

There are submonoids of $\Sigma^*$ at each level of the Chomsky hierarchy if $|\Sigma| \geqslant 2$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.