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
    $\begingroup$ "Deterministic Sausage Automoton" would be an excellent name for a band $\endgroup$ May 17 '20 at 2:12
  • $\begingroup$ @BenGrossmann There is a band named "Finite Automata" out there, but I guess there language isn't regular; en.wikipedia.org/wiki/Finite_Automata_(band) $\endgroup$
    – StefanH
    Aug 3 '20 at 12:51
  • $\begingroup$ @StefanH Close enough $\endgroup$ Aug 3 '20 at 12:57

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$$


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.