Keskustelu: Yleinen keskustelu: Formaalien kielten yhteydettömyydestä

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)!)

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.

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

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

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?

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.