Kirjautuminen

Haku

Tehtävät

Keskustelu: Yleinen keskustelu: Formaalien kielten yhteydettömyydestä

Benu87 [20.12.2010 10:50:43]

#

Hei
Mikä mahtanee olla helpoin tapa osoittaa L1 ja L2 leikkaus yhteydettömäksi, jos L1 on säännöllinen ja L2 yhteydetön? Yhdisteen osoitus löytyy monistakin oppimateriaaleista, mutta tähän ei tunnu löytyvän (ainakaan kovin helposti) selvää ohjetta.

(Mod. huom: Muista kertoa aihe (tässä formaalit kielet)!)

Antti Laaksonen [20.12.2010 10:55:57]

#

Tavallinen todistus on tehdä pinoautomaatti, jonka tila vastaa L1:n äärellisen automaatin tilan ja L2:n pinoautomaatin tilan yhdistelmää ja jonka pino vastaa L2:n pinoautomaatin pinoa.

Benu87 [20.12.2010 12:20:09]

#

Ja pieni korjaus edelliseen kysymykseen. Kyse oli L1 ja L2 unionista (L1UL2), ei leikkaukksesta.

Metabolix [20.12.2010 12:33:19]

#

Unioni ja yhdiste ovat sama asia, joten voit luntata suoraan oppimateriaalista.

Benu87 [20.12.2010 12:44:05]

#

Joo, mut tyhmällä meni noi tossa väärin päin. Alunperin piti kysyä: Mikä mahtanee olla helpoin tapa osoittaa L1 ja L2 unioni yhteydettömäksi, jos L1 on säännöllinen ja L2 yhteydetön?

Mutta olisi vielä toinen aiheeseen liittyvä kysymys:
Jos on jokin kieli L (esim palindromi) ja ensiksi pyydetään osoittaa että se on yhteydetön. Esim. S-> epsilon,a,b,aSa,bSb. Tämän jälkeen pyydetään osoittaa että L ei ole säännöllinen. Voidaanko tuo osoittaa vain säännöllisten kielten pumppauslemmalla tekemällä vastaoletus että kieli on säännöllinen, vai tarvitseeko osoitus tehdä yhteydettömien kielten pumppauslemmalla?

Antti Laaksonen [20.12.2010 14:32:30]

#

Benu87 kirjoitti:

Mikä mahtanee olla helpoin tapa osoittaa L1 ja L2 unioni yhteydettömäksi, jos L1 on säännöllinen ja L2 yhteydetön?

Jos L1 on säännöllinen, L1 on myös yhteydetön. Siis on olemassa yhteydetön kielioppi L1:lle ja L2:lle, ja niistä on helppoa tehdä uusi yhteydetön kielioppi, joka vastaa kielten yhdistettä.

Toinen tapa on todistaa asia pinoautomaattien avulla samalla tavalla kuin leikkauksen yhteydettömyys.

Benu87 kirjoitti:

Voidaanko tuo osoittaa vain säännöllisten kielten pumppauslemmalla tekemällä vastaoletus että kieli on säännöllinen, vai tarvitseeko osoitus tehdä yhteydettömien kielten pumppauslemmalla?

Säännöllisten kielten pumppauslemmalla voidaan osoittaa, että jokin kieli ei ole säännöllinen. Yhteydettömien kielten pumppauslemmalla voidaan osoittaa, että jokin kieli ei ole yhteydetön.

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Tietoa sivustosta