Is the intersection of two "sausage" languages also a "sausage" language?

111 Views Asked by At

Let's define a deterministic sausage automaton as a sextuple $V = (A, Q_L, Q_R, \phi, q, F)$, where $A$ is a finite input alphabet, $Q_L$ and $Q_R$ are left-states and right-states respectively, $\phi: (Q_L \cup Q_R) \times A \to (Q_L \cup Q_R)$ is transition function, $q \in (Q_L \cup Q_R)$ is the initial state and $F \subset (Q_L \cup Q_R)$ is the set of terminal states. We will define the automata function $\overline{\phi}: (Q_L \cup Q_R) \times A^* \to (Q_L \cup Q_R)$ using the following recurrence:

$$\overline{\phi}(q', \Lambda)=q'\forall q' \in (Q_L \cup Q_R)$$ $$\overline{\phi}(q', a \alpha)=\overline{\phi}(\phi(q', a), \alpha) \forall q' \in Q_L a\in A \alpha \in A^*$$ $$\overline{\phi}(q', \alpha a)=\overline{\phi}(\phi(q', a), \alpha) \forall q' \in Q_R a\in A \alpha \in A^*$$

We then say that the language accepted by $V$ is $L := \{\alpha \in A^*|\overline{\phi}(q, \alpha) \in F\}$. We call a formal language a sausage language iff it is accepted by some deterministic sausage automaton.

It is not hard to see, that all regular languages are sausage languages. However, the class of sausage languages is much larger (for example, the language of even-length palindromes is a sausage language but neither a regular language, nor even a deterministic context-free language). It is also not hard to see, that the complement of a sausage language is also a sausage language. But what's about the intersection? Is the intersection of two sausage languages also a sausage language?

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is no. The relevant languages are:

$$L = a^n b^n c^*$$

$$G = a^* b^n c^n$$

$$L \cap G = a^n b^n c^n$$

Both $L, G$ are recognizable by a variant of the even palendrome recognizer. Just strip off the end that doesn't need to be paired, then unpeel the first and last in pairs. However, we cannot recognize their intersection!

This is due to a variant of the pumping lemma: if we recognize an infinite language then our states space and update function must contain a loop. This loop implies that there's some finite string of appends and prepends we can do that keeps us in the language. Ie, for even palendromes we can "pump"

$$(a^n) s (a^n)$$

Onto any even length palendrome $s. $

If we look at $L \cap G,$ there's no such string. Once we have $abc$ there's nothing we can append and prepend to stay in the language. Therefore it's not recognizable.

Finally, as a bonus, note this implies we can't recognize unions either, as

$$ ( L^c \cap G^c)^c = L \cup G$$