Задача свързана с контекстно-свободнa граматикa

[complex]

Ще ви помоля да ми помогнете за следната задача:
G=?, така че L(G) = {aⁿb^m| n ≥ m} = {a^ka^mb^m|k, m ≥ 0}
R={S`-> SA, S -> ε, S -> aS, A -> ε, A -> aAb }

[Реклама]

[BeckhamStZ]

А какво е условието? Да се намери граматиката ли?

G' = L(G') = a*
G" = L(G") = { [tex]a^{n}b^{n}[/tex] | [tex]n \in N[/tex] }
G" = { {S}, {a,b}, S, { S -> [tex]\epsilon[/tex], S->aSb }

G = L(G) = L(G') . L(G")

от КДА A построяване на КСГ разпознаваща съответния език
G_A = < Q, ∑, S, {q₁ -> aq₂ | [tex]\delta[/tex](q₁,a)=q₂} U { q -> [tex]\epsilon[/tex] | [tex]q \in F[/tex]} >
=> G' = {q₀, {a,b}, q₀, { q₀ -> aq₀, q₀-> [tex]\epsilon[/tex]}

и се прави конкатенацията

[complex]

Мерси колега, разбрах ги
Ако може да помоля да ми помогнете и за следващата задача:
Да се докаже, че езикът не е контекстно-свободен.
L = {b^mc^kd^meⁿ | n > k}

[BeckhamStZ]

Това ще стане със Pumping lemma-та, ама само до тук мога да ти помогна още не съм я разбрал. Иначе откъде ги имаш тези задачи? Днеска на контролното ( СИ - ФМИ ) ни бяха такива задачите

[complex]

Хаха.. е точно от там, че писах некви глупости и ми е интересно как ще стане.. поне за изпита да ги напиша като хората.

[BeckhamStZ]

oo то и аз днеска нищо не направих ама и понеделник е ден...
аз днеска нищо не направих. коя група си?

[complex]

Така ли се решава задачата..?

{b^mc^kd^meⁿ | n > k}

1сл. m ≥ n > k
Нека n е числото от лемата и L e CF. Тогава w = b^mcⁿd^meⁿ⁺¹, тогава w=2n +1>n, следователно w = xyzuv, |yzu|≤n, |yu|≥1 и за всяко i е изпълнено xyⁱzuⁱv Є L.
1.1 |yzu| = b^k, тогава x = b^s, v = b^m-(k+s)cⁿd^meⁿ⁺¹, нека |yu|=b^p, като p ≥ 1, тогава при и i = 0 xy⁰zu⁰v = b^sb^k-pb^m-k-scⁿd^meⁿ⁺¹ = b^m-pcⁿd^meⁿ⁺¹ < w = b^mcⁿd^meⁿ⁺¹, т.к p≥1, следователно гори..
1.2 |yzu| = b^kc^t, x = b^m-k, v = c^n-td^meⁿ⁺¹ , нека |yu|_b=p, |yu|_c=q , т. че p+q ≥ 1, тогава при i = 0 xy⁰zu⁰v = b^m-kb^k-pc^t-qc^n-td^meⁿ⁺¹ = b^m-pc^n-qd^meⁿ⁺¹ < w = b^mcⁿd^meⁿ⁺¹, т.к в противан случай p = 0, q = 0 следователно гори..
2сл. n>k>m
Нека n е числото от лемата и L e CF. Тогава w = bⁿcⁿ⁺¹dⁿeⁿ⁺², тогава w=4n +3>n, следователно w = xyzuv, |yzu|≤n, |yu|≥1 и за всяко i е изпълнено xyⁱzuⁱv Є L.
1.1 - аналог.
1.2 - аналог.

[1-vi klas]

леле аз кви глупости си измислях на тая..дано поне за творчество има 50-тина стотни и 1 единица ,че успях да си намеря мястото, на което да седна + 50 стотни за 1-ва задача .. заслужавам 4