Название: Автоматы и формальные языки
Отправлено: RawonaM от декабря 8, 2011, 20:57
Отправлено: RawonaM от декабря 8, 2011, 20:57
Кто-нибудь в них разбирается?
Регулярен ли язык![[tex]L = \{a^ivb^j | 1 \leq j, i \geq 2j-2, v \in \{a,c,d\}*\}[/tex]](https://latex.codecogs.com/png.latex?L = \{a^ivb^j | 1 \leq j, i \geq 2j-2, v \in \{a,c,d\}*\} "L = \{a^ivb^j | 1 \leq j, i \geq 2j-2, v \in \{a,c,d\}*\}")
?
Регулярен ли язык
Название: Языки и автоматы
Отправлено: Тайльнемер от декабря 9, 2011, 04:21
Отправлено: Тайльнемер от декабря 9, 2011, 04:21
Предположим, что ![[tex]L[/tex]](https://latex.codecogs.com/png.latex?L "L")
регулярен.
Среди свойств регулярных языков есть такое: если![[tex]L_1, L_2[/tex]](https://latex.codecogs.com/png.latex?L_1, L_2 "L_1, L_2")
регулярны, то ![[tex]L_1\cap L_2,\; L_1^R[/tex]](https://latex.codecogs.com/png.latex?L_1\cap L_2,\; L_1^R "L_1\cap L_2,\; L_1^R")
регулярны. (![[tex]L_1^R[/tex]](https://latex.codecogs.com/png.latex?L_1^R "L_1^R")
— язык, состоящий из всех слов языка ![[tex]L_1[/tex]](https://latex.codecogs.com/png.latex?L_1 "L_1")
, записанных в обратном порядке.)
Язык![[tex]\{b^*a^*\}[/tex]](https://latex.codecogs.com/png.latex?\{b^*a^*\} "\{b^*a^*\}")
регулярен, следовательно, по свойству, язык ![[tex]N:=L^R\cap\{b^*a^*\}[/tex]](https://latex.codecogs.com/png.latex?N:=L^R\cap\{b^*a^*\} "N:=L^R\cap\{b^*a^*\}")
регулярен.
![[tex]N=\{b^ja^i\mid j\geqslant 1,\; i\geqslant 2j-2\}.[/tex]](https://latex.codecogs.com/png.latex?N=\{b^ja^i\mid j\geqslant 1,\; i\geqslant 2j-2\}. "N=\{b^ja^i\mid j\geqslant 1,\; i\geqslant 2j-2\}.")
Пусть![[tex]p[/tex]](https://latex.codecogs.com/png.latex?p "p")
— длина накачки языка ![[tex]N[/tex]](https://latex.codecogs.com/png.latex?N "N")
.
![[tex]b^pa^{2p-2}\in N[/tex]](https://latex.codecogs.com/png.latex?b^pa^{2p-2}\in N "b^pa^{2p-2}\in N")
, следовательно по лемме о накачке ![[tex]\exists\, \alpha,\gamma\in\mathbb Z^+\;\exists\,\beta\in\mathbb N\;\left[\alpha+\beta+\gamma=p \quad \wedge \quad \forall k\in\mathbb N\;[b^\alpha(b^\beta)^kb^\gamma a^{2p-2}\in N]\right][/tex]](https://latex.codecogs.com/png.latex?\exists\, \alpha,\gamma\in\mathbb Z^+\;\exists\,\beta\in\mathbb N\;\left[\alpha+\beta+\gamma=p \quad \wedge \quad \forall k\in\mathbb N\;[b^\alpha(b^\beta)^kb^\gamma a^{2p-2}\in N]\right] "\exists\, \alpha,\gamma\in\mathbb Z^+\;\exists\,\beta\in\mathbb N\;\left[\alpha+\beta+\gamma=p \quad \wedge \quad \forall k\in\mathbb N\;[b^\alpha(b^\beta)^kb^\gamma a^{2p-2}\in N]\right]")
.
Однако, при![[tex]k=2[/tex]](https://latex.codecogs.com/png.latex?k=2 "k=2")
имеем ![[tex]b^\alpha(b^\beta)^kb^\gamma a^{2p-2}=b^{p+\beta}a^{2p-2}\notin N[/tex]](https://latex.codecogs.com/png.latex?b^\alpha(b^\beta)^kb^\gamma a^{2p-2}=b^{p+\beta}a^{2p-2}\notin N "b^\alpha(b^\beta)^kb^\gamma a^{2p-2}=b^{p+\beta}a^{2p-2}\notin N")
, т. к. ![[tex]2p-2 < 2(p+\beta)-2[/tex]](https://latex.codecogs.com/png.latex?2p-2 < 2(p+\beta)-2 "2p-2 < 2(p+\beta)-2")
. Следовательно, изначальное предположение неверно, и язык нерегулярен.
Среди свойств регулярных языков есть такое: если
Язык
Пусть
Однако, при
Название: Языки и автоматы
Отправлено: RawonaM от декабря 9, 2011, 08:13
Отправлено: RawonaM от декабря 9, 2011, 08:13
Спасибо, Тайльнемер! Сегодня по дороге на работу как раз меня осенила мысль, что если перевернуть, то по лемме о накачке легко доказывается. А вчера я крутил-крутил, пытаясь напрямую доказать по той же лемме, но ничего не получалось. Возможно ли это вообще?
Название: Языки и автоматы
Отправлено: Тайльнемер от декабря 9, 2011, 08:48
Отправлено: Тайльнемер от декабря 9, 2011, 08:48
Цитата: RawonaM от декабря 9, 2011, 08:13Вряд ли. Лемму, конечно, можно переформулировать для такого случая: w=xyz, |yz|≤p.
Возможно ли это вообще?
Название: Автоматы и формальные языки
Отправлено: RawonaM от декабря 20, 2011, 19:56
Отправлено: RawonaM от декабря 20, 2011, 19:56
Дан регулярный язык L. Нужно доказать, что ![[tex]L'=\{w\in \Sigma*|ww^R \in L\}[/tex]](https://latex.codecogs.com/png.latex?L'=\{w\in \Sigma*|ww^R \in L\} "L'=\{w\in \Sigma*|ww^R \in L\}")
тоже регулярен.
Доказательство: построим недетерминированный автомат принимающий L'. Пусть![[tex]A=(\Sigma,Q,q_0,F,\delta)[/tex]](https://latex.codecogs.com/png.latex?A=(\Sigma,Q,q_0,F,\delta) "A=(\Sigma,Q,q_0,F,\delta)")
детерминированный автомат, принимающий L.
Определим![[tex]B=(\Sigma,Q\times Q \cup \{p_0\},p_0,F_B,\mu)[/tex]](https://latex.codecogs.com/png.latex?B=(\Sigma,Q\times Q \cup \{p_0\},p_0,F_B,\mu) "B=(\Sigma,Q\times Q \cup \{p_0\},p_0,F_B,\mu)")
.
![[tex]\mu(p_0,\epsilon)=\{q_0\}\times F[/tex]](https://latex.codecogs.com/png.latex?\mu(p_0,\epsilon)=\{q_0\}\times F "\mu(p_0,\epsilon)=\{q_0\}\times F")
Для каждых![[tex]q,r\in Q , \sigma \in \Sigma[/tex]](https://latex.codecogs.com/png.latex?q,r\in Q , \sigma \in \Sigma "q,r\in Q , \sigma \in \Sigma")
![[tex]\mu((q,r),\sigma)=\{\delta(q,\sigma)\}\times \{s\in Q|\delta(s,\sigma)=r\}[/tex]](https://latex.codecogs.com/png.latex?\mu((q,r),\sigma)=\{\delta(q,\sigma)\}\times \{s\in Q|\delta(s,\sigma)=r\} "\mu((q,r),\sigma)=\{\delta(q,\sigma)\}\times \{s\in Q|\delta(s,\sigma)=r\}")
Вот только что-то я не догоняю какие состояния будут принимающими.
![[tex]\{(q,q)|q\in Q\}[/tex]](https://latex.codecogs.com/png.latex?\{(q,q)|q\in Q\} "\{(q,q)|q\in Q\}")
или ![[tex]F\times \{q_0\}[/tex]](https://latex.codecogs.com/png.latex?F\times \{q_0\} "F\times \{q_0\}")
?
Доказательство: построим недетерминированный автомат принимающий L'. Пусть
Определим
Для каждых
Вот только что-то я не догоняю какие состояния будут принимающими.
Название: Автоматы и формальные языки
Отправлено: RawonaM от декабря 21, 2011, 10:14
Отправлено: RawonaM от декабря 21, 2011, 10:14
Цитата: RawonaM от декабря 20, 2011, 19:56А все, дошло, первый вариант правилен. Я все язык путал.
Вот только что-то я не догоняю какие состояния будут принимающими.
Название: Автоматы и формальные языки
Отправлено: RawonaM от января 20, 2012, 08:34
Отправлено: 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]](https://latex.codecogs.com/png.latex?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\} "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\}")
.
Нужно построить автомат с магазинной памятью без переходов-эпсилон, принимащий этот язык.
Я затрудняюсь потому что с одной стороны нужно считать сколько a в каждой группе, поэтому нужно впихивать в стек много символов, с другой стороны когда нужно будет найти нужное значение можно будет снимать только по одному символу со стека на каждый символ ввода (т.к. нельзя применять переходы-эпсилон), и поэтому по-моему будет достаточно символов.
Нужно построить автомат с магазинной памятью без переходов-эпсилон, принимащий этот язык.
Я затрудняюсь потому что с одной стороны нужно считать сколько a в каждой группе, поэтому нужно впихивать в стек много символов, с другой стороны когда нужно будет найти нужное значение можно будет снимать только по одному символу со стека на каждый символ ввода (т.к. нельзя применять переходы-эпсилон), и поэтому по-моему будет достаточно символов.
Название: Автоматы и формальные языки
Отправлено: RawonaM от января 20, 2012, 14:33
Отправлено: RawonaM от января 20, 2012, 14:33
Дошло, вопрос снят.
Название: Автоматы и формальные языки
Отправлено: RawonaM от февраля 16, 2012, 07:42
Отправлено: RawonaM от февраля 16, 2012, 07:42
Цитата: Тайльнемер от декабря 9, 2011, 08:48Оказывается это вполне возможно, просто нужно взять i=0 и все в порядке.Цитата: RawonaM от декабря 9, 2011, 08:13Возможно ли это вообще?Вряд ли.