9. Automaty skończone#
9.1. Zadania dodatkowe#
Ćwiczenie 9.4
Określić jaki język regularny \(L\) definiuje następujące wyrażenie regularne: \(11^*(0+1)1+0 .\) (wyrażenie \(1^*\) definiuje język \(\{\varepsilon,1,11,111,\ldots\}\), gdzie \(\varepsilon\) - słowo puste)
Ćwiczenie 9.5
Dla języka regularnego \(L\) zdefiniowanego w zadaniu 1. zbudować diagram skończonego automatu deterministycznego (niedeterministycznego), który go akceptuje.
Ćwiczenie 9.6
Narysować diagram skończonego automatu deterministycznego, który akceptuje ciągi binarne z parzystą liczbą \(1 .\)
Ćwiczenie 9.7
Narysować diagram skończonego automatu deterministycznego nad alfabetem \(\{x,y\}\), który akceptuje język zdefiniowany przez następujące wyrażenie regularne: \(x^*y(x+y)x^*y .\)
Ćwiczenie 9.8
Narysować diagram skończonego automatu niedeterministycznego nad alfabetem \(\{a,b\}\), który akceptuje język \(L=\{a^nba^mb\colon n\geq 0, m>0\}\cup \{a^nbba^mb\colon n,m\geq 0\}\), dla \(n,m\in\mathbb{N}\cup\{0\} .\)
Ćwiczenie 9.9
Podać wyrażenie regularne, które definiuje język nad alfabetem \(\{0,1\}\) akceptowany przez następujący automat deterministyczny \(\mathcal{A}=(S=\{s_0,s_1,s_2,s_3,s_4,s_5\},\{0,1\}, \sigma,s_0,\{s_5\})\) z funkcją przejścia \(\sigma\colon S\times \{0,1\}\to S\):
σ |
0 |
1 |
|---|---|---|
s₀ |
s₀ |
s₁ |
s₁ |
s₂ |
s₃ |
s₂ |
s₂ |
s₄ |
s₃ |
s₃ |
s₄ |
s₄ |
s₅ |
s₅ |
s₅ |
s₅ |
s₅ |
Ćwiczenie 9.10
Narysować diagram automatu deterministycznego nad alfabetem \(\{a,b\}\), który akceptuje słowa o parzystej liczbie \(a\) oraz parzystej liczbie \(b .\)
Informacja
Materiały na tej stronie przygotowała Agata Pilitowska.
Projekt „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.
Zadanie 7 pn. „Pilotażowa realizacja innowacyjnej ścieżki kształcenia obejmującej znaczny komponent zespołowych zajęć projektowych we wczesnej fazie studiów” realizowane w ramach projektu „NERW 2 PW. Nauka - Edukacja - Rozwój - Współpraca” współfinansowany jest ze środków Unii Europejskich w ramach Europejskiego Funduszu Społecznego.
