9752257317

Wykład 1, str. 6

[języMbmialn^

Przykład: (nieformalny)

(a, aback, abandon, abase, ..., zoom}

—    język (skończony) składający się ze słów języka angielskiego

{0, 1, 10, 11, 100, 101, ...}

—    język (nieskończony) składający się z liczb binarnych

jaⁿóⁿ|n>oj = {A, ab, aabb, aaabbb,...}

—    język (nieskończony) składający się z takich słów, w których

•    występują tylko litery a i b,

•    liczba liter a jest równa liczbie liter b,

•    wszystkie litery a poprzedzają wszystkie litery b.

Wykład 1, str. 7

^Języl^omialn^

DEFINICJA:

E — skończony niepusty alfabet, czyli zbiór tzw. liter słowo — dowolny ciąg skończonej długości o elementach z E E* — zbiór wszystkich słów język — dowolny zbiór słów L CE*

Przykład: nie mylić! —

A — słowo puste (ciąg liter o długości 0) Uwaga: to nie jest litera! |

0 = {} —język pusty (nie zawierający żadnego słowa)

A = {A} — język zawierający wyłącznie słowo puste Przykład:

1(*2 — 1)(1 — (2 — *1)() — słowo nad alfabetem E = {(, ),—,*, 1,2} {A, a, b, ab, ba}—język nad alfabetem E = {a, b} zawierający pięć słów jaⁿ |n > oj = (A, a, aa, aaa, ...}—jęz. nieskończ. nad alf. E = {a}