Gramatika -> regex

Question

1

asked 2014-11-15 20:48:32 +0100

gandalf
113 ●27 ●30 ●37

Ahojte, chcel by som poprosit este o radu, kde mam chybu. Snazim sa previest gramatiku na regularny vyraz. Tu je zadanie

  S-> aE | aS | bS | aA | eps
  A -> aA
  B -> a
  C -> a | b | aA | bE
  D -> aD | bD | bB | bA
  E -> bD

A takto postupujem ja

  S = aE + aS + bS + **aA** + eps
  **A = aA**
  B = a
  C = a + b + **aA** + bE
  D = aD + bD + bB + **bA**
  E = bD

tucne resp. medzi hviezdickami su nepotrebne stavy

Tu dosadzujem

D = (a + b)D  + ba = (a + b)* ba
E = b(a + b)*ba
C = a + b + b[b(a + b)*ba ]
S = (a+b)* a [a + b + b[b(a + b)*ba ]]

Podla vysledku mi to vsak nesedi, ten by mal byt

S=(a+b)*(ab(a+b)*ba+eps)

Viete mi niekto poradit? Dakujem.

Comments

Asi jsi někam dosadil C místo E? Protože C se v tý gramatice nikde nepoužívá.

Viktor Chlumský ( 2014-11-15 21:11:13 +0100 )edit

Asi jsi někam dosadil C místo E? Protože C se v tý gramatice nikde nepoužívá.
Viktor Chlumský ( 2014-11-15 21:11:13 +0100 )edit

Accepted Answer

2

answered 2014-11-16 08:34:52 +0100

Jan Rubín
265 ●9 ●17 ●24

C nikde nepoužíváš (není v S ani jinde). Zbytek (D, E) máš určený správně. Takže když dosadíme:

S = ab(a+b)*ba + aS + bS + eps

Vyjde nám po úravě:

S = (a+b)S + ab(a+b)*ba + eps
S = (a+b)*(ab(a+b)*ba + eps)

Pokud bys s tím měl ještě problém, tak mi sem napiš do komentářů a já ti to vypracuji podrobně na papír, nicméně až večer..

Super dakujem, je mi to jasne :)

gandalf ( 2014-11-16 13:17:59 +0100 )edit

@gandalf: Označíš odpověď jako správnou? Pomocí té fajfky pod hodnocením. Díky

Miro Hrončok ( 2014-11-18 06:36:30 +0100 )edit