# Irreducible languages

This is not necessarily a research question. Just a question out of curiosity:

I am trying to understand if one can define "irreducible" languages. As a first guess I call a language L "reducible" if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $A\cap B = \emptyset$, $P \cap C = \emptyset$ and $A\cdot B = C\cdot P$, then there exists a language $B' \cap P = \emptyset$ such that $B = B'\cdot P$? This would correspond in integers to the lemma of Euklid and would be usefull to prove uniqueness of "factorization".

2) Is it true that every language can be factored in a finite number of irreducible languages?

If someone has a better idea on how to define "irreducible" language, I would like to hear it. (Or is there maybe already a definiton of this, which I am unaware of?)

• "if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$," where ​ $\cdot$ ​ is ... ​ ​ ​ ​
– user6973
Jul 27, 2016 at 18:00
• $\cdot$ is concatenation
– user35803
Jul 27, 2016 at 18:06
• You may be interested in the paper "Prime Languages", although it is a different notion: cs.huji.ac.il/~ornak/publications/mfcs13.pdf Jul 28, 2016 at 10:46

Here's a counterexample to this:

call a language L "reducible" if it can be written as $$L = A \cdot B$$ with $$A \cap B = \emptyset$$ and $$|A|,|B|>1$$, otherwise call the language "irreducible". Is it true:

1) If P is irreducible, A,B, C are languages such that $$A\cap B = \emptyset$$, $$P \cap C = \emptyset$$ and $$A\cdot B = C\cdot P$$, then there exists a language $$B' \cap P = \emptyset$$ such that $$B = B'\cdot P$$?

In the unary alphabet $$\{0\}$$, define the following words $$a=0^4,\quad b=0,\qquad c=0^3,\quad p=0^2.$$ Then $$ab=cp$$ and it is not the case that $$b=b'p$$ for any $$b'$$.

So we get a counterexample with the singleton languages $$P=\{p\},\quad A=\{a\},\quad B=\{b\},\quad C=\{c\}.$$

There is the notion of primality of a language. It asks whether L can be written as $L_1 \cdot L_2$ where neither factor contains the empty word. A language is prime if it cannot be written in this form.