Lambda ma sens gdy nie jest w zlozeniu

Czyli abb^ = abb = ^abb = ab^b

V - alfabet

V* - słownik

Np. V = {a,b}

V* = { ^, a,b,aa,ab,ba,bb,aaa … } - słownik

ab i ba to dwa rozne slowa

l(x) - długość slowa

l(^) = 0

porządek leksykograficzny u < v , u,v naleza V*

porządek zupełny u<v lub v<u

slowo transponowane

x = kolos

x^T = solok

x = x1,x2,x3,x4

x^T = xn, xn-1 …..

(x*y)^T = y^T * x ^T

^^T = ^

Transpozycja jezyka

Usuwanie lambda produkcji

Np

Zamiast lambdy wstawiam A i dodaje do reszty

Czyli powstaje :

S -> AB| B bo (A=^)B = B

B-> BB|1|^

A-> 1A0|10

Eliminuje B -> ^ i dodaje do reszty

S-> AB|B|A| ^ bo A*^ = A i B->^ = ^

B-> BB|1|B B -> jest bezuzyteczna wiec skleslam

A->1A0|10

Eliminuje S -> ^

S-> AB|B|A

B-> BB|1

A->1A0|10

Gramatyka bezkontekstowa nazywamy monotoniczna jeżeli prawe strony regul produkcji maja dlugosc wieksza od 1. - czyli ma być taka ze po prawej stronie maja być minimum 2 symbole ;-)

Postac normalna chomskiego i greibacha

PROJEKT

6. Wyznaczyć język bezkontekstowy będący konkatencja, sumą lub domknięciem Kleene'ego L1 i L2

Masz L1={ab,bb} i L2={a,cb}

konkatencja L=L1*L2 czyli L={aba,abcb,bba,bbcb}

suma L=L1+L2 czyli L = {ab,bb,a,cb}

domkniecie Kleeene'ego L1*={lambda,ab,bb,abbb,abab,bbab,bbbb,....}

Domknięciem Kleene'ego dowolnego alfabetu jest język złożony ze wszystkich słów nad tym alfabetem. Przykładowo jeśli
, to
jest zbiorem wszystkich ciągów zerojedynkowych o skończonej długości.

7.Wyznaczyć gramatyke bezkontekstową dla danego języka skończonego.(zwrocić uwage na całe te opisy itd)

8.Podać wyrażenie regularne opisujące dany język skończony.

mamy np. L = {a, b, ab, aab, abababa}

najprostsze wyrażenie dla tego języka: |a + b + ab + aab + abababa|

algorytm: zamieniamy przecinki na plusy a klamerki na | - gotowe ;]

9. wzorki C Y K

10. C Y K projekt

11. Dane związki regularne przekształcić do zadanej postaci wykorzystując związki w algebrze wyrażeń regularnych.

12.

Wg wykładu najpierw się zmienia A na K wszędzie po prawej stronie, a potem dopiero (już po zmianie) dopisuje K-produkcje identyczne jak A-produkcje. Czyli tak jak ktoś już zrobił wcześniej:

A->aA|bC

Zmieniam A na K po prawej:

A->aK|bC

Dopisuje K z przepisanymi regułami z A:

A->aK|bC

K->aK|bC

13.

16.

Gramatyka regularna to gramatyka wyglądająca następująco:

S->aB|aC|bS

B->a|aB

C->b

tzn. w regułach produkcji po prawej stronie jeden symbol terminalny poprzedza jeden symbol nieterminalny, lub jest jeden symbol terminalny.

gdy symboli terminalnych po prawej stronie będzie więcej, np. A->ab. Z definicji nie jest, ale można ją przekształcić do regularnej, więc opisuje ona język regularny.

Jeżeli gramatyka jest regularna to jest i bezkontekstowa i kontekstowa i rekurencyjnie przeliczalna.

Gramatyka bezkontekstowa to taka, w której po lewej stronie masz jeden symbol nieterminalny, a po prawej dowolną produkcję, np:

S->SBA|a|lambda

A->aA|B|a <- nie jest regularna!

B->b

Gramatyka bezkontekstowa jest szczególnym przypadkiem gramatyki kontekstowej o kontekście zerowym, jak jest bezkontekstowa albo kontekstowa to i jest rekurencyjnie przeliczalna.

Gramatyka kontekstowa to coś takiego:

aB->aC

tzn. po lewej stronie jest reguła produkcji zawierające lewy lub prawy kontekst (lub też oba jednocześnie - chyba!)

Jak jest kontekstowa to nie jest bezkontekstowa i nie jest regularna, ale jest rekurencyjnie przeliczalna.

W kontekstowej jest coś jeszcze, chyba że kontekst musi stać po tej samej stronie w produkcjach. Pisali o tym wcześniej cichy i mcczester, ja nie kumam tego do końca. Dlatego na temat sprawdzania czy jest kontekstowa czy nie - nie będę się rozpisywał. Zaznaczę tylko że czy jest kontekstowa, sprawdzamy tylko gdy nie jest bezkontekstowa. Bo jak jest bezkontekstowa to automatycznie jest i kontekstowa.

Rekurencyjnie przeliczalna jest gdy jest którą kolwiek z wyżej wymienionych. Gramatyka nie jest rekurencyjnie przeliczalna jeżeli po lewej stronie stoi lambda

lambda->A

Wtedy nie jest żadną z wymienionych gramatyk.

---