Czy język jest regularny

Zdania. Tautologie. Język matematyki. Wszelkie zagadnienia związane z logiką matematyczną...
Kondzio333
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 16 lis 2021, o 18:29
Płeć: Mężczyzna
wiek: 22

Czy język jest regularny

Post autor: Kondzio333 »

Witam zastanawiam się czy język
\(\displaystyle{ L = \left\{ 0^{j - 1}1 0^{j + 1} : j \ge 2 \right\} }\) jest regularny?
Alfabet: {0, 1}

Zacząłem to robić, wyszło mi że nie jest regularny czy zrobiłem to dobrze?
Mój tok myślenia (korzystam z twierdzenia Myhilla-Nerode'a):
Rozpatrzam dwa słowa \(\displaystyle{ w = 0^{k - 1}1 0^{k + 1} }\) oraz \(\displaystyle{ v = 0^{k - 1 + c}1 0^{k + 1} , c \ge 1}\)
Zatem roznicym sufiksem jest \(\displaystyle{ u = 0^{c} }\) następnie konkatenujemy nasze słowa w, v z sufiksem u.
Dla \(\displaystyle{ (konkatenacja) wu = 0^{k - 1}1 0^{k + 1 + c} }\) wiemy, że \(\displaystyle{ c \ge 1}\) zatem \(\displaystyle{ wu }\) NIE NALEŻY DO \(\displaystyle{ L }\) Jest ok?
ODPOWIEDZ