Regulární výrazy
Tento projekt je vhodný zejména pro studenty, kteří navštěvují či navštěvovali kurzy IB102 nebo IB005. Teoretické základy nutné k pochopení zadání však nejsou nijak složité a ten, kdo je pochopí před zapsáním výše jmenovaných předmětů, si jistě nijak neuškodí.
Regulární výrazy jsou způsobem, jak definovat množiny slov. Jejich definici naleznete opět např. na Wikipedii či ve studijním textu k formálům (zejména kapitola 2.2.4).
Množina regulárních výrazů je definována rekurzivně:
- ∅, ε a libovolné písmeno abecedy jsou regulární výrazy
- jsou-li R a S regulární výrazy, pak R+S, R.S, R*, R+ jsou regulární výrazy
Tedy například (a+b+ε).(c + d)* je regulární výraz. Významem (sémantikou) regulárního výrazu R je jazyk L(R), tj. množina slov, která výrazu R odpovídá.
| výraz — R | význam — L(R) |
|---|---|
| ∅ | ∅ |
| ε | {ε} (ε je prázdné slovo, tj. slovo délky nula.) |
| a (a je libovolné písmeno abecedy) | {a} |
| S+T | L(S) ∪ L(T) |
| S.T | { uv | u ∈ L(S), v ∈ L(T)} |
| S+ | { u1…un | ∃ n > 0, ∀ ui ∈ L(S) } |
| S* | {ε} ∪ L(S+) |
Vaším úkolem je zadefinovat vhodný datový typ k reprezentaci regulárních výrazů, zvolit formát vstupu a implementovat jeho načítání. Dále pak definovat funkce pro převod regulárního výrazu na konečný automat (zde se předpokládá buď rozumný textový výstup, nebo spolupráce s řešiteli projektu Konečné automaty a použití jejich datového typu).
Odhadovaný počet řešitelů: 2.