Context Free Languages

[werewolf]

cuna, kam nje ushtrim ne Theory of Computation qe nuk po me vete mendja si ta zgjidh (kam nja 3 ore qe po bej ushtrime dhe spo punon me truri tani )

Te ndertohet nje Context Free Grammar per { a^i b^j c^k | i=j either j=k; i,j,k>=0}

Mendime?

[IlirDeda]

Provo dicka te tille:

S -> S1 | S2

S1 -> AB
A -> aAb | e
B -> cB | e

S2 -> DC
D -> aD | e
C -> bCc | e 

[qoska]

automata gje e bukur por pak komplekse zgjidhja qe ka bere iliri eshte me se e sakte, nqs nuk je i qarte se cfare do te thote B -> cB | e do te thote qe B shkon ne vargu i pare
B -> cB -> ccB ... etj dhe gjithashtu shkon edhe ne (e) diagramen ose grafin nuk di si te ta vizatoj ne kete text box te forumit gjithsesi besoj ta kesh kuptuar.

[werewolf]

Falemnderit ilir, por ajo nuk e ben ate qe kerkoj, sepse gjeneron dhe stringen abc, ose stringen boshe qe nuk duhet te gjenerohen, sepse duhet ose i=j, ose j=k, jo te dyja, pra i=j=k nuk duhet te beje pjese ne gjuhen e gjeneruar!
gjithesesi faleminderit!

[werewolf]

... pyeta profesorin, nuk ishte OR ekskluziv (mund te ishin dhe te treja te barbarta). Une kisha derguar nje CFG te ngjashem me ate qe kishte bere Iliri (pothuaj jane njesoj), me futen friken kot, me thane qe nuk duhej i=j=k.
Ushtrimi kerkonte dhe te thoje nese eshte 'ambiguous' ose jo, qe behet shume thjesht(mjafton nje shembull):

CFG:

S --> AB | CD
A --> aAb| e
B --> cB | e
C --> aC | e
D --> bDc | e

Per te treguar nese eshte ambiguous, mjaftojme qe te gjejme nje stringe
 qe gjenerohet ne 2 menyra te ndryshme duke perdorur 'leftmost derivation'

S-->AB-->aAbB-->abB-->abcB-->abc
S-->CD-->aCD-->aD-->abDc-->abc

pra eshte 'ambiguous'!

te drejte ke qoska, e bukur eshte (sidomos Turing Machines)!

[cunimartum]

Menyre me vizuale dhe me e qarte per te vertetuar qe nje CFG eshte Ambigous eshte te derivosh dy Parse Trees te ndryshme.

Nga ana tjeter kujdes nese te duhet te vertetosh qe nje CFG nuk eshte Ambigous, eshte gabim i zakonshem per nxenesit e rinj ta vertetojne duke ndertuar dy Parse Trees te njejta edhe pse njera mund te jete ndertuar me LeftMost derivation dhe tjetra RightMost