Strona główna

1. Języki formalne


Pobieranie 41.76 Kb.
Data20.06.2016
Rozmiar41.76 Kb.

1.Języki formalne
RZYKŁADY

Przykład 1.1.

Udowodnij, że dla dowolnych języków formalnych zachodzi inkluzja

. (*)

Rozwiązanie

Załóżmy, że oraz niech słowo A należy do domknięcia . Wynika stąd, że

istnieją słowa , takie, że . Skoro , to

,

co mieliśmy pokazać.

Przykład 1.2.

Wykaż, że dla dowolnego języka formalnego zachodzi równość



. (**)

Rozwiązanie

Ponieważ więc z własności (*) wynika, że .

Pokażemy, że . Niech słowo A należy do domknięcia . Wynika stąd, że

istnieją słowa , takie, że . Skoro , to istnieją słowa takie, że . Stąd



,

co mieliśmy pokazać.


Przykład 1.3.

Niech . Pokaż, że .



Rozwiązanie

Zauważmy, że język zawiera się w języku , a więc na mocy implikacji (*) z Przykładu 1.1 mamy:



.

Z drugiej strony, ponieważ



to język zawiera się w domknięciu . Stąd z warunku (*) z Przykładu 1.1 wynika, że a ponieważ więc



.

Z wykazanych inkluzji otrzymujemy żądaną równość .




ZADANIA

Zadanie 3.1

Określ długość słowa w alfabecie:

a)

b)

c)

d)



Zadanie 3.2

Wskaż alfabety nad którymi można utworzyć język

a)L – zbiór numerów komórkowych

b)L – zbiór możliwych adresów www

c)L = ℤ

d)L = ℝ

Zadanie 3.3

Niech . Z ilu słów składa się język:

a)L={zbiór liczb parzystych należących do przedziału (19, 300) }

b)L={zbiór liczb czterocyfrowych podzielnych przez 9 }

c)L={zbiór liczb trzycyfrowych których cyfra dziesiątek jest liczbą nieparzystą}

d)L={ zbiór liczb pięciocyfrowych podzielnych przez 4 lub 25 }

Zadanie 3.4

Dane są słowa , . Transpozycja którego z nich jest równa

Zadanie 3.5

Niech i . Wypisz wszystkie słowa języka L i L2 . Opisz domknięcia tych języków.

Zadanie 3.6


Dane jest słowo . Wypisz wszystkie jego przedrostki, podsłowa i przyrostki jeśli:


a)

b)

Zadanie 3.7

Niech L będzie dowolnym językiem nad alfabetem . Definiujemy język:



.

Określ z ilu słów składa się język PRZEDROSTKI (L), jeśli

a)

b)

Zadanie 3.8

Niech , . Wskaż słowa o długości 5 należące do języka

Zadanie 3.9

Niech , . Wyznacz wszystkie słowa należące do języka:


a)

b)

c)

d)

e)

f)

g)

h)



Zadanie 3.10

Określ własności dodawania, składania i mnożenia języków. Które z tych działań są wewnętrzne, łączne przemienne.

Zadanie 3.11


Niech i . Na ile sposobów można zapisać słowo AL*, jeżeli


a)

b)

Zadanie 3.12

Wykaż, że do domknięcia języka należą wszystkie słowa o długości większej niż 3. Opisz język

Zadanie 3.13

Niech . Opisz język:


a)

b)

c)

d)



Zadanie 3.14

Znajdź język L nad alfabetem jeśli wiadomo, że jego domknięcie ma postać:

a)

b)

Zadanie 3.15

Wypisz wszystkie słowa o długości 10 należące do języka:


a)MNOŻENIE,

b)DODAWANIE

c)MNOŻENIEPALINDROMY

d)DODAWANIEPALINDROMY

Zadanie 3.16

Opisz język

a)MNOŻENIE NPALINDROMY,



b)DODAWANIE PPALINDROMY,

Zadanie 3.17


Niech , . Wyznacz


a)

b)

c)

d)



Jakie relacje zachodzą między językami jeśli

e)

f)

g)

h)

Zadanie 3.18

Pokaż, że nie są prawdziwe następujące zdania

a)Jeżeli to

b)Jeżeli to lub

Zadanie 3.19

Jakie relacje zachodzą między językami:



a)

b)

c)

d)



Zadanie 3.20

Określ, które zdanie jest prawdziwe dla dowolnych języków formalnych

a)

b)

c)

d)

Zadanie 3.21

Znajdź alfabet ∑ dla którego mają miejsce równości języków:

a)PPALINDROMY NPALINDROMY = NPALINDROMY

b)PRZEDROSTKI(L) = PRZYROSTKI(L), dla dowolnego L

Zadanie 3.22

Niech . Opisz język



a)

b)

c)

d)




Zbiór zadań z TPI | Aneta Tomaszewska







©snauka.pl 2016
wyślij wiadomość