8299308550
• jeśli w jest spleceniem słowa s ze słowem t, to jest również spleceniem słowa t ze słowem s
• jeśli v = at, a € A i w jest spleceniem słowa s ze słowem t to aw jest spleceniem słowa s ze słowem v
Dla danych dwóch języków L\, L2 C A* zdefiniujmy ich splecenie jako zbiór wszystkich w, które są spleceniami pewnego s € Li z pewnym t G L2.
Czy splecenie dwóch języków regularnych zawsze jest językiem regularnym?
Czy splecenie dwóch języków bezkontekstowych zawsze jest językiem bezkontekstowym?
Niech A będzie skończonym alfabetem i niech L C A*- Przez Lustro(L) będziemy w kolejnych trzech zadaniach rozumieli język {wvR € A* : wv € L}
Zadanie 66. Pokaż, że jeśli L jest regularny, to Lustro(L) również jest regularny.
Zadanie 67. Pokaż, że deterministyczny automat skończony rozpoznający język Lustro(L) może potrzebować liczby stanów wykładniczo większej niż deterministyczny automat skończony rozpoznający język L.
Zadanie 68. Czy teza Zadania 66. pozostanie prawdziwa, jeśli oba wystąpienia słowa „regularny” zmienimy w nim na „bezkontekstowy” ?
Niech języki Lyw i Lyw będą zdefiniowane jak w Zadaniach 34 - 36.
Zadanie 69. Załóżmy, że L jest CFL, zaś w jest pewnym ustalonym słowem z E*. Czy wynika z tego że Lyw jest CFL?
Zadanie 70. Załóżmy, że L jest CFL, zaś w jest pewnym ustalonym słowem z S*. Czy wynika z tego że L^w jest CFL?
Przez język rodzynkowy będziemy przez chwilę (to znaczy w kolejnych trzech zadaniach i ani chwili dłużej) rozumieć język będący podzbiorem La-ba‘-
Dla danego języka regularnego L napis i(L) będzie oznaczał na tej liście indeks języka L, czyli minimalną liczbę stanów deterministycznego automatu rozpoznającego L.
Zadanie 71. Czy istnieje język rodzynkowy L taki, że L* jest bezkontekstowy ale nie jest regularny?
Zadanie 72. Dla ustalonego n naturalnego niech Ln będzie językiem składającym się ze wszystkich słów postaci 0*60?, gdzie 0 < i,j < 2n oraz |ż — j\ < 1. Udowodnij, że «(L*) szacuje się (z dokładnością do stałej multiplikatywnej) przez n2 .
Wskazówka: Warto rozważyć słowa postaci ak(ba2n)1, dla odpowiednich liczb kil.
Zadanie 73. Udowodnij, że dla każdego naturalnego n istnieje język rodzynkowy Ln, taki że i(LnLn) > c2*(Ln), gdzie c jest pewną stałą niezależną od n. Jeśli nie potrafisz pokazać takiego wykładniczego dolnego ograniczenia na wzrost i(LnLn), to dostaniesz punkty również za inne ograniczenie, jeśli nie będzie mniejsze niż c*(Lre)3.
O języku A C £* powiemy, w kolejnych trzech zadaniach, że jest konfluentny, jeśli: Viu, 3i e E* Vy e E* (wxy € A <*=>■ vxy e A).
9
Wyszukiwarka
Podobne podstrony:
Kosztowne zbieranie danych Przyczyną braku troski o użytkowników jest również to, że zbieranie
skanuj0070 Cechą podatku jest również to. że ma on charakter świadczenia pieniężnego. Ponieważ współ
3c 10. Jeżeli test jest trafny to wynika stad, że jest również a)
27 (456) 52 i drugim, po dwie niewiadome, z których Jedną jest również reakcja Rg. Uzyskaliśmy to dz
DSC00164 Owa notatka sekcji But to des Moulins jest również - nic wprost - dowodem na to, że w przyp
Kolendowicz07 ■ Załóżmy teraz, że otrzymana linia ugięcia jest również sinusoidą (jest to drugie
społeczeństwa jest również to, że resocjalizacja się nie udaje52. To zawsze sam więzień resocjalizuj
DSC36 (5) Znieczulenia nym jest również to, że w czasie znieczulenia ogólnego podtlenek azotu podaw
Jeśli otwarty układ sterowania jest stabilny to będzie również stabilny po zamknięciu w przypadku:
nie zatrzymano panu/i dokumentu, to może się to stać przy każdej kontroli. Wiadomo, że taka osoba je
10_r_- Istotne jest również to, że wśród kompozycji teatralnych Grzywacza znalazła się muzyka zarówn
10_r_- Istotne jest również to, że wśród kompozycji teatralnych Grzywacza znalazła się muzyka zarówn
148 J JURCZAK, J KUENSKI, J J ZIÓŁKOWSKI jest również wysoko punktowane przez KBN (Tabela 7). Reszta
więcej podobnych podstron