Графовые представления регулярных выражений

Постройте $G(r)$ для $r=(11+0)^{*}(00+1)^{*}$.

Постройте $G(r)$ для $r=a^{*} b\left(c+d a^{*} b\right)^{*}$.

Какова кратчайшая строка в каждом из следующих языков? Какова кратчайшая непустая строка в каждом языке?

Найдите представления в виде размеченных орграфов для следующих регулярных выражений:

Определите регулярные выражения, представляемые орграфами на рисунке 1.7.

Рисунок 1.7: Три орграфа к упражнению 4.

Найдите простейший орграф, представляющий $\varepsilon$.

Найдите контрпримеры, показывающие, что теорема 1.25 неверна, если убрать требования о том, что $u$ должна быть нефинальной вершиной, а $v$ — неначальной вершиной.

Теорема 1.25: Пусть $r$ — регулярное выражение. Тогда $\varepsilon$-ребро $(u, v)$ в $G(r)$, являющееся единственным исходящим ребром из нефинальной вершины $u$ или единственным входящим ребром в неначальную вершину $v$, можно стянуть в одну вершину, сохранив при этом свойство теоремы 1.23. (Если один из концов $\varepsilon$-ребра является начальной или конечной вершиной, то таковой является и получившаяся вершина.)