# How to find prefixes and suffixes for infinite languages? (Automata)

L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}


It's easy to find suffixes and prefixes for finite Regular languages. But what will be the approach for infinite Regular languages?

For example:-

Alphabet = {a,b}

L1 = Every string starts with a.
L2 = Every string ends with a.
L3 = {waw|w belongs to {a,b}^*}/ every string contains at least one a.


What will be the Suffixes and Prefixes for the given Regular languages and how to find them?

• Please clarify a few things. What you mean by "find"? Why is there an "(Automata)" in the title, are your languages supposed to be given as automata? If so, what kind of automata? Are the two occurrences of w in your L3 the same, contrary to the comment?
– Kai
Nov 10, 2023 at 15:33
• By find I mean how to write. I put Automata in the title because it's the topic of Automata theory. Yes w is same for both occurences. Nov 10, 2023 at 17:16
• That L3 is not regular. The comment suggests the (regular) language $L_3 = \{~waw'~|~w,w'\in \{a,b\}^*~\}$.
– Kai
Nov 12, 2023 at 10:23

For regular languages this is relatively straighforward. Let $$L\subseteq\Sigma^*$$ be regular. Let $$A = (Q, \Sigma, q_0, \delta, F)$$ be an NFA that recognises $$L$$. Construct another NFA $$A' = (Q, \Sigma, q_0, \delta, F')$$ from $$A$$ by changing just the final state set as follows: set $$F'$$ to the set of all states in $$Q$$ from which a state in $$F$$ can be reached by any number of transtions in $$\delta$$. This makes $$A'$$ accept the language of prefixes of $$L$$.

For the suffix construction, realise that suffixes are reversed prefixes of reverse words in $$L$$. Wikipedia explains how to reverse a regular language.

Let's see what others say but I think you could adapt the algorithm that enumerates the sentences of a language and restrict it to enumerate prefixes or suffixes only. I assume you are familiar with formal languages, the algorithm I sketched takes advantage of standard notation and well-known techniques.

An algorithm for enumerating the sentences of a possibly infinite context-free language $$\mathcal{L_0}$$ is the following (notice I stated the language has to be context-free or the algorithm will require exponential time and space to run; also the very first step will be inapplicable).

Let $$\mathcal{G}$$ be a context-free grammar such that $$\mathcal{G}=(T,N,\Sigma,S,P)$$ and $$\mathcal{L}(\mathcal{G})=\mathcal{L_0}$$. Let $$K$$ be the maximum length of the sequences you want to enumerate.

1. Convert $$\mathcal{G}$$ to CNF (Chomsky Normal Form) obtaining $$\mathcal{G'}=(T,N',\Sigma,S',P')$$,
2. declare $$q$$ a queue of symbols (terminal and non-terminal),
3. insert $$S'$$ in $$q$$,
4. while there are elements in $$q$$:
5. take the head sequence $$s$$, remove it and scan it:
6. if $$s$$ does not contain non-terminal symbols or is $$s=\epsilon$$ or $$\vert s\vert=K$$, give it as output.
7. conversely, if it does contain some non-terminal replace the leftmost non-terminal symbol $$n$$ with the RHSs of the all productions $$p\in P . n \rightarrow \alpha$$, generating (possibly many) new sequence(s) $$\{s_0,...,s_k\}$$,
8. enqueue sequences $$s_0,...,s_k$$.
9. goto 4.

This algorithm will behave differently depending on the grammar you provide.

1. If you run it on a grammar whose language is finite and $$K$$ is large enough, it will generate all sentences. In case $$K$$ is smaller than the longest sentence of the language it will provide some mangled sentences (that is, containing non-terminal symbols).

2. In case the language is infinite it will not get stuck enumerating one sentence, it will operate a rewrite step on some sequence and then switch to the next one, enforcing progress.

3. If the grammar is ambiguous, sentences having two (or more) distinct derivation trees will be given as output two (or more) times.

I think you could employ this algorithm for generating $$prefixes$$, and the version replacing the rightmost non-terminal in step 7. to generate $$suffixes$$.

The first step where I convert to CNF is required to avoid an explosion of the queue during the rewriting phase. CNF is characterized by the property of having RHSs of at most 2 non-terminal symbols. Considering you replace a non-terminal with some RHS, the length of the string taking the place of the removed symbol is at most two. Hence, each time you rewrite you will add only one symbol at most to each sequence. This approach makes the algorithm practical.