Нероде-релација

Нероде-релација (такође Нероде-конгруенција или нероде-конгруенција здесна) је релација еквиваленције која се примељује у теорији формалних језика. Њоме се речи неког формалног језика деле на класе еквиваленције.

Дефиниција

Нека је дат формални језик L над азбуком Σ. Две речи из Σ^* су у нероде-релациији ~ акко се обе могу формирати преко идентичних суфикса на речи из језика L. Формално записано, за сваке u и v из Σ^* важи:

$u\sim v\quad \Longleftrightarrow \quad \forall w\in \Sigma ^{*}:\ uw\in L\Leftrightarrow vw\in L$