HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Arden's Lemma in case $X_{i}=AX_{i}$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
caseax_lemmaarden

Problem

Arden's lemma is applied in cases where we have an equation that looks like this: $$ X_{i}=AX_{i} + B, $$ with the condition that $\epsilon \notin A$.

But if I have such situation: $$X_{i}=AX_{i},$$ so there's no B, or simply talking we have $B= \varnothing $, thus by the Lemma, we have $$X_{i}=A^{*}\cdot\varnothing$$ which equals to $$X_{i}=\varnothing.$$

Is my reasoning correct?

Solution

What we have with

$\qquad X = AX + B$

is, quite literally, a recurrence of languages expressed in terms of the symbolic method. $B$ represents the base case of the recurrence. Arden's Lemma just tells you that the smallest fixpoint of this recurrence (read as an inductive definition) is $A^*B$.

Now, if you drop the base case and only have

$\qquad X = AX$,

there are no finite words that can be constructed in this way. Now, the "recurrence" may make sense read as a coinductive definition (that is the solution would be an $X$ containing infinite strings) but not as an inductive one. Hence, the empty set is the only one that solves the equation.

Context

StackExchange Computer Science Q#65089, answer score: 5

Revisions (0)

No revisions yet.