Искам да знам, че като се има предвид нормален език L, който съдържа само звезден оператор Kleene (напр. (ab)*), възможно ли е L да бъде генериран чрез конкатенация на два нередовни езика? Опитвам се да докажа, че L може да бъде генериран само от конкатенацията на два редовни езика.
Благодаря.
Това твърдение е невярно. Разгледайте тези два езика над = {a}:
L1 = { an | n е степен на две } { }
L2 = { an | n не е степен на две } { }
Нито един от тези езици не е правилен (първият може да се докаже, че е неправилен с помощта на теоремата на Myhill-Nerode, а вторият е тясно свързан с допълнението на L1 и също може да се докаже, че е нередовен.
Аз обаче ще твърдя, че L1L2 = a*. Първо, имайте предвид, че всеки низ в конкатенацията L1L2 има формата an и следователно е елемент от a*. След това вземете произволен низ в a*; нека бъдеn. Ако n е степен на две, то може да се образува като конкатенация на an от L1 и от L2. В противен случай n не е степен на две и може да се образува като конкатенация на от L1 и an от L2 . Следователно L1L2 = a*, така че теоремата, която се опитвате да докажете, е невярна.
Надявам се това да помогне!
