Automaty skończone (skończenie stanowe)

Wstęp notatki wygenerowany automatycznie

...Podstawowe informacje o automatach skończenie stanowych, językach regularnych, korektach ortografii

´ Automaty skonczone ´ Def. Automat skonczony definiuje sie jako piatke ¸ ¸ ¸ ´ ´ ´ É – skonczony zbior stanow, É ¦ Æ Õ¼ , gdzie ¦ – alfabet (wej´ ciowy), s Æ É ¢ ¦ ¾É – funkcja przej´ c, s´ Õ¼ ¾ É – stan poczatkowy, ¸ ´ ´ ´ É – zbior stanow koncowych. 1 ´ Automaty skonczone: przykład automatu ½ É ¦Æ¼ Æ ¦ É ¼½¾¿ ¿ 0 1 2 3 4 5 ½ ¾¿ ¾ b 2 0 b 3 a 1 c 4 c ½ 5 2 ´ Automaty skonczone: uwagi notacyjne ¯ stany bedziemy oznacza´ liczbami całkowitymi nieujemnymi (w literaturze czesto spotyka c sie oznaczenia Õ¼ Õ½ Õ¾ ¸ ¸ ¸ ) ¸ ¸ ¸ ¸ ¸ ´z ¯ stan poczatkowy na rysunku bedzie wyro˙ niony pogrubiona linia (bedzie to zawsze stan ). ´ ´z ´ ¯ stany koncowe beda na rysunku wyro˙ nione podwojna linia ¸ ¸ ¸ ¸ ¼ 3 ´ Automaty skonczone: jezyk automatu ¸ ´ ´ Mowimy, ze automat skonczony akceptuje słowo ½ ¾ ˙ s Ò, je´ li istnieje w nim ´ z scie˙ ka etykietowana kolejnymi symbolami tego słowa, prowadzaca od stanu ¸ ´ ´ z z c z poczatkowego do stanu koncowego (na scie˙ ce tej mo˙ e by´ te˙ dowolnie wiele ¸ przej´ c przez ). s´ ´ ´ Zbior wszystkich słow akceptowanych przez automat nazywamy jezykiem au¸ tomatu (jezykiem akceptowanym/definiowanym przez automat ) i oznaczamy ¸ Ä . ´ µ Automat ½ akceptuje jezyk ¸ a(b+c+). 4 ´ ´ ´ Automaty skonczone: rownowa˙ nosc automatow z ´´ ´ ´ O dwoch automatach mowimy, ze sa rownowa˙ ne, je´ li jezyki akceptowane ˙ z s ¸ ¸ ´ przez jeden i drugi sa rowne: ¸ ´ ½ ¾ ¸ Ä ´ ½µ Ä ´ ¾µ np. b 2 0 b b 3 0 b a 1 2 a 1 c 4 c c 3 5 c ½ 5 ¾ ´ Automaty skonczone: najwa˙ niejsze podklasy z ¯ ¯ ´ automaty skonczone bez -przej´ c s´ ´ automaty skonczone deterministyczne 6 ´ Automaty skonczone: deterministyczne ´ ´ Deterministycznym automatem skonczonym nazywamy automat skonczony spełniajacy warunki: ¸ 1. nie posiada -przej´ c ( Õ...

Podobne notatki