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

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

Дефиниција

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

$u\sim v⟺\mathrm{\forall }w\in {\mathrm{\Sigma }}^{*}:uw\in L\iff vw\in L$