Автоматы и формальные языки

RawonaM · декабря 8, 2011, 20:57

Кто-нибудь в них разбирается?
Регулярен ли язык $[tex]L = \{a^ivb^j | 1 \leq j, i \geq 2j-2, v \in \{a,c,d\}*\}[/tex]$ ?

Тайльнемер · декабря 9, 2011, 04:21

Предположим, что $[tex]L[/tex]$ регулярен.
Среди свойств регулярных языков есть такое: если регулярны, то регулярны. ( — язык, состоящий из всех слов языка , записанных в обратном порядке.)
Язык регулярен, следовательно, по свойству, язык регулярен.
$[tex]N=\{b^ja^i\mid j\geqslant 1,\; i\geqslant 2j-2\}.[/tex]$
Пусть $[tex]p[/tex]$ — длина накачки языка $[tex]N[/tex]$ .
$[tex]b^pa^{2p-2}\in N[/tex]$ , следовательно по лемме о накачке .
Однако, при $[tex]k=2[/tex]$ имеем , т. к. . Следовательно, изначальное предположение неверно, и язык $[tex]L[/tex]$ нерегулярен.

RawonaM · декабря 9, 2011, 08:13

Спасибо, Тайльнемер! Сегодня по дороге на работу как раз меня осенила мысль, что если перевернуть, то по лемме о накачке легко доказывается. А вчера я крутил-крутил, пытаясь напрямую доказать по той же лемме, но ничего не получалось. Возможно ли это вообще?

Тайльнемер · декабря 9, 2011, 08:48

Цитата: RawonaM от декабря 9, 2011, 08:13
Возможно ли это вообще?

Вряд ли. Лемму, конечно, можно переформулировать для такого случая: w=xyz, |yz|≤p.

RawonaM · декабря 20, 2011, 19:56

Дан регулярный язык L. Нужно доказать, что $[tex]L'=\{w\in \Sigma*|ww^R \in L\}[/tex]$ тоже регулярен.

Доказательство: построим недетерминированный автомат принимающий L'. Пусть $[tex]A=(\Sigma,Q,q_0,F,\delta)[/tex]$ детерминированный автомат, принимающий L.
Определим $[tex]B=(\Sigma,Q\times Q \cup \{p_0\},p_0,F_B,\mu)[/tex]$ .

$[tex]\mu(p_0,\epsilon)=\{q_0\}\times F[/tex]$

Для каждых $[tex]q,r\in Q , \sigma \in \Sigma[/tex]$
$[tex]\mu((q,r),\sigma)=\{\delta(q,\sigma)\}\times \{s\in Q|\delta(s,\sigma)=r\}[/tex]$

Вот только что-то я не догоняю какие состояния будут принимающими.
$[tex]\{(q,q)|q\in Q\}[/tex]$ или $[tex]F\times \{q_0\}[/tex]$ ?

RawonaM · декабря 21, 2011, 10:14

Цитата: RawonaM от декабря 20, 2011, 19:56
Вот только что-то я не догоняю какие состояния будут принимающими.
$[tex]\{(q,q)|q\in Q\}[/tex]$ или $[tex]F\times \{q_0\}[/tex]$ ?

А все, дошло, первый вариант правилен. Я все язык путал.

RawonaM · января 20, 2012, 08:34

Дан язык $[tex]L=\{a^{i_1}ba^{i_2}b...a^{i_n}bc^ta^{i_{n-t+1}}| 1\leq n; \forall k (1\le k \le n): i_k \ge 1; 1 \le t \le n\}[/tex]$ .

Нужно построить автомат с магазинной памятью без переходов-эпсилон, принимащий этот язык.

Я затрудняюсь потому что с одной стороны нужно считать сколько a в каждой группе, поэтому нужно впихивать в стек много символов, с другой стороны когда нужно будет найти нужное значение можно будет снимать только по одному символу со стека на каждый символ ввода (т.к. нельзя применять переходы-эпсилон), и поэтому по-моему будет достаточно символов.

RawonaM · января 20, 2012, 14:33

Дошло, вопрос снят.

RawonaM · февраля 16, 2012, 07:42

Цитата: Тайльнемер от декабря 9, 2011, 08:48
Цитата: RawonaM от декабря 9, 2011, 08:13Возможно ли это вообще?
Вряд ли.

Оказывается это вполне возможно, просто нужно взять i=0 и все в порядке.

Лингвофорум

Автоматы и формальные языки

RawonaM

Тайльнемер

RawonaM

Тайльнемер

RawonaM

RawonaM

RawonaM

RawonaM

RawonaM

Быстрый ответ