Недетерминированные конечные автоматы.

Пусть A⁰– недетерминированный конечный автомат.

A⁰= <P⁰,S⁰,s₀⁰,φ⁰,F⁰>

F⁰– множество конечных подмножеств алфавита состояний.

S = {S₀ , S₁ , S₂}

M(S) = {{ S₀ } , { S₁ } , { S₂ } , { S₀ , S₁} , { S₀ , S₂} , { S₁ , S₂} , { S₀ , S_{1 ,} S₂}}

M^* <= M

φ:P*SS– детерминированный алфавит

φ⁰:P*SM^*- недетерминированный автомат

Отличие недетерминированного автомата состоит в том, что функции перехода может определять не одно состояние, в которое переходит автомат, а некоторое подмножество состояний.

ТЕОРЕМА:ЕслиL(A⁰) – язык который допускается некоторым конечным автоматомA⁰, то существует детерминированный конечный автоматAкоторый допускает этот же язык.