---
title: "Automaty skończone"
lecture_number: 8
has_solutions: false
has_exercises: true
---

```{include} ../_includes/sagecell-loader.md
```

# Automaty skończone

## Zadania dodatkowe

::::{exercise}
:class: [exercise]

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)

::::

::::{exercise}
:class: [exercise]

Dla języka regularnego $L$ zdefiniowanego w zadaniu 1. zbudować diagram skończonego automatu deterministycznego (niedeterministycznego), który go akceptuje.

::::

::::{exercise}
:class: [exercise]

Narysować diagram skończonego automatu deterministycznego, który akceptuje ciągi binarne z parzystą liczbą $1 .$

::::

::::{exercise}
:class: [exercise]

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 .$

::::

::::{exercise}
:class: [exercise]

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\} .$

::::

::::{exercise}
:class: [exercise]

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₅ |

::::

::::{exercise}
:class: [exercise]

Narysować diagram automatu deterministycznego nad alfabetem $\{a,b\}$, który akceptuje słowa o parzystej liczbie $a$ oraz parzystej liczbie $b .$

::::

```{include} ../_includes/titlepage-info.md
```