Loading [MathJax]/extensions/tex2jax.js
Ask Your Question
1

Rozstřel -L1 . L3 = L2, L3 musí být regulární

asked Jan 8 '16

cozzy gravatar image

updated Jan 8 '16

Zdravím,

koukám na rozstřel a jedna otázka mi není jasná. Konkrétně řádky 78 a 79 v této tabulce:

docs.google.com/spreadsheets/d/1pWnr-cX-1qeCbIHFRRGQqTzX5YQLGK19X8Xhm48eH80/edit#gid=0

(Pardón. Nemám dostatečnou karmu abych mohl použít tak pokročilou věc jako je odkaz :D)

Je to správně? Nenapadá mě neregulární jazyk, který by po zřetězení s regulárním tvořil jazyk regulární.

add a comment

1 Answer

Sort by » oldest newest most voted
2

answered Jan 8 '16

updated Jan 8 '16

Tak mějme třeba jazyk L1 = a*, L2 = aaa*. Bez debat jsou oba regulární. Dále si vezmeme jazyk L3 = a^p (p je prvočíslo). O tomto jazyku můžeme snadno dokázat, že regulární není. L1.L3 a L3.L1 jsou oba jazyky, kde je počet písmen a větší než dvě, tedy jazyk L2. Takže ano, zřetězením regulárního L1 a neregulárního L3 máme regulární L2.

link

Comments

Že mě to nenapadlo... Stejně tak to půjde třeba pro L3 = a^(k^2). Díky moc

cozzy (Jan 8 '16)
add a comment

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: Jan 8 '16

Seen: 308 times

Last updated: Jan 08