Matematické Fórum

kulicka · 16. 10. 2015 09:14

Ahoj,
poradí mi někdo jak to dokázat?

Definujme následující jazyk nad abecedou ${0, 1}^{*}$ :
D = {w | w obsahuje stejný počet výskytů podslov 01 a 10}.

Například slovo 101 patří do D, protože 101 obsahuje jednou 01 a jednou 10, ale například
slovo 1010 nepatří do D, protože 1010 obsahuje dvakrát 10, ale jen jednou 01.

Ukažte, že D je regulární jazyk.

Vím, že by se to mělo dokázat regulární gramatikou nebo konečným automatem. Mi ale spíš přijde, že regulární není, protože jak si mám pamatovat počet výskytů jednotlivých podslov?

Dokázala bych to tedy pomocí Pumping lemma:
$w=(01)^{n}(10)^{n} \in D$

$x=(01)^{k} \nl y=(01)^{l};l>0 \nl z=(01)^{n-k-l} (10)^{n}$

$w=xy^{i}z$

pro i=2:
$w=(01)^{k}((01)^{l})^{2}(01)^{n-k-l} (10)^{n}= (01)^{k}(01)^{2l}(01)^{n-k-l} (10)^{n}= (01)^{k+2l+n-l-k}(10)^{n}=(01)^{n+l}(10)^{n}$

protože l>0, tak $n+l \neq n$ , tudíž z PL není regulární.

Je to tak?
Díky.

byk7 · 16. 10. 2015 09:23

↑ kulicka:

Pozor, slovo $w=(01)^{n+l}(10)^n$ obsahuje $(n+l)+(n-1)$ podslov $01$ a $(n+l-1)+n$ podslov $10$ . (Prostě proto, že řetězec 0101 ti vygeneruje 10 (uprostřed).)

kulicka · 16. 10. 2015 09:39

↑ byk7:
Tudíž je regulární? Ale jak potom udělat gramatiku/automat?

Nebo mám jen špatně rozdělené slovo pro Pumping lemma?

byk7 · 16. 10. 2015 10:46

↑ kulicka: Pozor, Pumping lemma se používá pro důkaz, že daný jazyk není regulární. Pokud chceš dokazovat, že nějaký jazyk regulární je, pak ti to lemma nepomůže. V zadání je, že máme ukázat regulárnost jazyka D. Já bych na to zkusil jít přímo z definice na Wikipedii (https://cs.m.wikipedia.org/wiki/Regul%C … 3%AD_jazyk), tj. najít takové regulární jazyky, jejichž 'spojením' dostaneš D. (jen nápad :)

kulicka · 16. 10. 2015 11:22

↑ byk7:
No dobře, ale mě není jasné, jak si udržovat kolik bylo podslov 01 a 10? Protože jestli má každý stav (neterminál) reprezentovat počet jednotlivých podslov (rozdíl), tak jich přece může být kdo ví kolik, což dopředu nevím...

jarrro · 17. 10. 2015 15:04

nikdy som nebol nejako zvlášť dobrý v týchto veciach, ale
neznamená rovnaký výskyt len to, že ak chceme aktuálne "dobré" slovo končiace na 0 rozšíriť 1 tak musíme pridať aj nulu a končiace na 1 ak chcem rozšíriť nulou pridať aj jednotku?
je to len hlasné rozmýšľanie a tiež otázka na skúsenejších

Matematické Fórum

#1 16. 10. 2015 09:14

Regulární gramatika

#2 16. 10. 2015 09:23

Re: Regulární gramatika

#3 16. 10. 2015 09:39

Re: Regulární gramatika

#4 16. 10. 2015 10:46

Re: Regulární gramatika

#5 16. 10. 2015 11:22

Re: Regulární gramatika

#6 17. 10. 2015 15:04

Re: Regulární gramatika

Zápatí