2016-02-14

Set-top-box k O2TV pro další televizi zdarma

Dostal se ke mně zajímavý úkol: Jeden z klientů, kterému se starám o IT infrastrukturu mě požádal o konzultaci k zakoupení dalšího O2TV přijímače k další televizi, kterou má doma. Technicky nebylo možné koupit jednoduše a draze nový tuner, ale sestavil jsem jiné řešení, které bylo zdarma. Protože se z toho vyvinul docela zajímavý projekt, tak by byla škoda se o něj nepodělit se svými čtenáři.

Pokud si nechcete přečíst poutavou omáčku, skočte na technické řešení níže, na konci je pak nějaké souhrnné zamyšlení.

Nejprve uvedení do problematiky: O2TV je placená služba společnosti O2, která vám zprostředkuje příjem televizního signálu prostřednictvím jejich internetového připojení, které jede nejčastěji přes technologii VDSL. V principu tedy přijímáte televizní signál přes telefonní dráty. (což je samo o sobě docela legrační)



Platí se to jako služba a podle mě je to příšerně drahé na to, jak je to zbytečné. Běžné pozemní digitální vysílání (DVB-T) se dá dneska i v železobetonové zástavbě chytnout na anténu za 50 Kč namísto měsíčních 400 Kč za O2TV. (pokud tedy vůbec sledujete televizi) Jenže, pokud jste sportovní fanda, tak vám nic jiného nezbude, protože O2 zakoupila všechna vysílací práva na český, anglický a já nevím ještě jaký fotbal, takže už to nebude vysílat veřejně Česká televize a musíte si pořídit tuto službu, což je i popisovaný případ, proč si klient pořídil O2TV.

Doma má běžný xDSL modem ze kterého je rozveden internet ethernetem po celé obrovské prvorepublikové vile. Zažil jsem si tam horké chvilky už s touto kabeláží, neboť původně to (ne)jelo jen na modemu a WiFi repeateru. Po přepracování se mi podařilo dostat na 3 routery (už byly koupené) s AP pro zajištění konektivity v domě. Proč to zmiňuji? Modem leží v obýváku a hned vedle je hlavní TV ke které je připojený O2TV tuner, takže s první instalací nebyl vůbec problém. 



Jenže se objevila potřeba připojit i druhou televizi v patře (každý přece rád sleduje filmy z postele), ale z důvodu technického řešení je potřeba tuner připojit do prvního modemu, což bylo nějakých 30 metrů daleko. Tento drobný detail mi také málem unikl, naštěstí mám s modemy od O2 bohaté zkušenosti a tak jsem se rozpomněl na barevné značení portů.



Proč to tak je? O2TV neteče k vám domů stejným virtuálním okruhem jako internet (což ovšem neznamená, že ho nezpomaluje, protože dráty jsou jenom jedny). Řešeno je to pomocí technologie ATM (popisoval jsem je tady), která končí právě v modemu, kde je hranice mezi "velkým internetem" a vaší lokální sítí. TV tuner se potřebuje dostat k tomuto okruhu, který je v prvním modemu, přičemž vysílat televizní okruh dále do sítě rozumně nelze.

Takže co s tím? Oficiálním řešením je opravdu natáhnout další ethernetový kabel přes 4 místnosti a patro. Tento návrh však není paní domu povolen, prý už je tam kabelů dost a navíc AP s WiFi je nedaleko. Majitel se naštěstí rozvzpomene, že dostal od O2 přihlášení do O2TV GO a hned je jasno, kam další vývoj povede. O2TV GO je webové rozhraní k televiznímu vysílání nezávisle na poloze uživatele. Je tedy možné sledovat TV na mobilu či notebooku. Otázka zní, jak dostat obraz do televize, aby byl alespoň částečně zachován princip televizního přístroje.



Technicky

V tuto chvíli (1/2018) jsem měl problémy s během původního doplňku do Kodi (asi nějaká aktualizace), nicméně nabízí se nová varianta řešení, která je výrazně jednodušší a tím je Chromecast. Majitel má totiž dobrý (aktuální) telefon s Androidem a tak může díky tomuto zařízení streamovat obsah z mobilní aplikace O2TV do TV přes Chromecast, což značně usnadňuje celou komplexitu ovládání z postele. Navíc je to výrazně technicky/energeticky/kabelově jednodušší řešení. Doporučuji tedy zakoupit za cca 1200 Kč Google Chromecast a streamovat do něj O2TV z telefonu s Androidem, kde je aplikace O2TV.

Původní řešení s Kodi však ponechávám přístupné:
Analýza mě zavedla k bezplatné linuxové nástavbě XBMC nyní zvanou KODI se kterou jsem si už dříve hrál. Jde o software na principu Windows Media Center, tedy maximálně zjednodušené ovládání vhodné pro obrazovky televizí. Do tohoto prostředí existuje doplněk video.o2tvgo od vývojáře Štěpána Orta, který zajistí připojení O2TV, zbývá jenom domyslet, jak to celé zprovoznit.



Hledal jsme vhodné zařízení. Protože jde o pilotní projekt, který je určen k uživatelskému testování, tak jsem vybral jako hostitele starý notebook Lenovo 3000 C200 zde ve verzi s Intel Core 2 Duo a díky vykuchání jiného notebooku i s 3 GB RAM namísto původních 512 MB. Protože podkladovým operačním systémem je Kodibuntu a jiné, tak je soustava dost dobře přenositelná i na jiné platformy než x86-64, zejména tedy ARM o tom ale později.



Instalaci linuxové OS zvládne i "slepice, pokud nasypete zrní kolem enteru". Pokud si soustavu přepnete do čestiny (System => Settings => Appearance => International => Language), tak zvládnete přidat také O2TV doplněk z flash disku (Systém =>Nastavení => Doplňky => Instalovat doplněk ze zip souboru), tím by mohla být soustava hotova, zbývá ji jen připojit k TV za pomocí VGA kabelu na obraz a propojky dvou 3,5 mm jacků pro zvuk. Pokud máte k dispozici HDMI, tak to bude lepší volba. Jak jistě tušíte s vyladěním je práce více.




Připojení Kodi k WiFi

Ať jsem hledal jak jsem chtěl, v menu jsem neviděl možnost připojit pomocí WiFi. Pro nastavení WiFi se totiž musíte přihlásit v desktopovém prostředí, tedy opustit XMBC rozhraní. Popisují to následující obrázky:



Rozhraní Kodi zavřete v levém dolním rohu tlačítkem vypnout, dále pokračujete možností "ukončit", tím dojde k odhlášení.



Na další obrazovce přepnete v pravém horním rohu rozhraní Kodi na Lubuntu kam se přihlásíte stejným jménem a heslem, jako jste zadali při instalaci.



Po naloadování plochy najdete v pravém dolním rohu ikonu připojení k síti, kde si vyberete svou WiFi síť do které se za pomocí průvodce přihlásíte.



Po dokončení se odhlásíte přes tlačítko vypnout (opět pravý dolní roh) možností odhlásit se.



Na přihlašovací obrazovce se přepnete do rozhraní Kodi a přihlásíte jménem a heslem. Teď už bude XBMC přihlášeno přes WiFi. Změny provedete opět tímto postupem, protože zde chybí správce z prostředí.


Dálkový ovladač

Jednou z podmínek soustavy bylo, že princip zůstane podobný běžnému TV přístroji ovládání, tedy nesmí zůstat pouze na notebooku. Naštěstí to v XMBC už vyřešili, stačí si stáhnout aplikaci z Google Play, případně AppStore a mít připojený notebook a telefon ke stejné lokální síti (přes mobilní internet to nepojede).



Komu by se nechtělo (nemohl) instalovat aplikaci, tak lze zapnout ovládání přes webové rozhraní. Poté stačí naťukat v mobilu (opět ve stejné síti) IP adresu notebooku http://0.0.0.0:8080, ovládání je takto krkolomnější, zato pojede všude.




Bez chytrého telefonu se ale dá obejít zakoupením nějakého hardwarového ovladače. Proč to ale komplikovat...

Automatické spuštění TV

Je poněkud nepohodlné, když je při každém zapnutí notebooku nutné se doklikat ke spuštění doplňku. Naštěstí v Kodi lze autostart skriptem spustit rovnou doplněk. Zde už se ale zachází do linuxové podstaty systému. Pokusím se to popsat tak, aby to zvládl i laik.



Ze zapnutého Kodi proveďte klávesovou zkratkou CTRL + ALT + F1 přepnutí do konzolového zobrazení. (zpátky CTRL + ALT + F7) Zde se přihlásíte stále stejným jménem a heslem.



Zadejte příkaz ls -la a podívejte se, zda-li se ve vaší složce nachází skrytá složka .kodi, pokud ano pokračujte příkazy 
cd .kodi/userdata/
nano autoexec.py
otevře se textový editor (a automaticky se vytvoří soubor)  do kterého vepíšete následující dva řádky
import xbmc
xbmc.executebuiltin('RunAddon(plugin.video.o2tvgo)')
zkratkou CTRL + O soubor uložíte a CTRL + X zavřete. Po restartování vás tak přivítá automaticky spouštěný doplněk O2TV. Ještě by to chtělo, aby se po spuštění rovnou také zapnula nějaká TV stanice, protože takto to zůstane viset na seznamu stanic, což není příliš pohodlné. (na této úpravě pracuji)

Účet superuživatele

Protože už jsme dostali do terminálového prostředí, budeme potřebovat oprávnění roota pro některé operace. Je to naštěstí snadné, přihlaste se běžným uživatelem a pak si v interaktivním režimu nastavte toto další heslo. Příkaz zní: 
sudo passwd root

Nastavení napájení

Jelikož nechci, aby mi při přehrávání TV svítil displej notebooku, který navíc nelze za pomocí funkčních tlačítek na klávesnici zhasnout, tak bych chtěl, aby se při sklopení víka alespoň neuspal a přehrávání dále běželo. To je možné snadno nastavit. Přihlašte se účtem superuživatele a pokračujte příkazem: 
nano /etc/systemd/logind.conf
kde změňte následujcí řádky
HandleLidSwitch=ignore
HandePowerKey=hibernate
případně i nějaké jiné podle svých preferencí a opět uložte pomocí CTRL+O a ukončete CTRL+X, pro aplikování změn proveďte restart notebooku.




Nastavení hlasitosti

Zdálo se mi, že notebook má při každém spuštění poměrně nízkou hlasitost a nepamatuje si její zvýšení. Tak jsem na to šel bez servítek a při každém spuštění se hlasitost nastaví natrvdo na 90% maximální. Jemnou regulaci lze stejně provádět na televizi ovladačem nebo pomocí mobilního telefonu.



Pod právem superuživatele si otevřete konfigurační soubor příkazem 
nano /etc/rc.local
a před řádek exit 0 vepište příkaz 
amixer set 'Master' 90%

Nastavení obrazovky

Poslední věc, kterou zbývá udělat před definitivním spuštěním do provozu je připojit televizi a nastavit správné rozlišení obrazu, což může být trochu problém zejména s ohledem na to, že pravděpodobně také používáte nějaké staré zařízení jako přehrávač.



V ostrém provozu mi usnadňuje to, že starší televize LG 42 PJ350 má stejné maximální rozlišení jako notebook (1024x768). V testovacím prostředí mám však TV s FullHD, kde mi vadilo rozplácnutí obrazu. Problém je prostá duplikace obrazu na více cílů, kterou provádí Kodi. Naštestí lze nastavit, že LCD TV je zdroj primární a podle té se deformuje obraz na monitoru počítače, kde to nevadí. Tak jak na to?
Systém => Nastavení => Systém =>Video výstup => Monitor
kde VGA1 je výstup na televizi v požadovaném rozlišení a LVDS1 je DVI rozhraní obrazovky notebooku. V nabízených možnostech jste limitováni tím, co umí grafická karta notebooku.




Praktické zkušenosti

Jsou zatím příliš krátké, ale největší obtíže dělá probuzení soustavy dálkovým ovladačem - na WiFi to je docela problém. Dále spuštění stále obsahuje poměrně hodně kroků: otevřít notebook, zapnout jej, zapnout TV, přepnout vstup, vybrat kanál, zavřít notebook, otevřít aplikaci, což jak cítíte není moc pohodlné, navíc doplněk O2TV není také softwarově úplně dodělaný, což komfortu nepřidává.


Budoucnost projektu

V průběhu oživování mě napadlo postupně mnoho myšlenek, jak projekt posunout dále. Pokud odmyslíme softwarovou implementaci O2TV doplňku v Pythonu, pak je největší možnost pokroku v hardwaru na kterém běží a související architektuře.



Začal bych asi od Raspberry PI, které je pro toto použití jako dělané. Ještě vhodnější je Raspberry PI Zero, se svou velikostí totiž může zůstat viset na kabelech za TV. Evolucí by pak mohla být nějaká HDMI tyčinka jako Intel Compute Stick či Chromecast a podobné. (u nich už bohužel cena roste nahoru) A co takhle nechat běžet Kodi na NASu, Turrisu či jinde a přenášet přes DLNA pouze obraz? To už je ale opravdu výživné "scifi"...



Všemi těmito úpravami vlastně přidávám chytrost do hloupých televizí, ale co když už chytrou televizi máte? (já ji nemám, nemohu otestovat) Záleží, co v ní běží za systém. Největší výhodou by bylo do ní nativně dostat XBMC alias Kodi, jenže to může být problém (minimálně kvůli záruky). Většina chytrých televizí ovšem podporuje instalaci Android aplikací. Bohužel je zde problém v tom, že v katalozích aplikací se nacházejí jen očesané verze O2TV GO bez možnosti přijímat živé vysílání. V mobilní aplikaci pro telefony to jde - že by stačilo APK nainstalovat na TV? Obávám se, že to bude také docela oříšek. 



Vzhledem k tomu, kolik se mi doma povaluje již jinak nevyužitelného hardwaru, je pro mě zajímavá právě možnost jejich zužitkování jako rozhraní pro chytré televize. Dokonce jsem zvažoval nasazení operačního systému Windows 8 Embedded jako podkladu, ale u nich už roste výpočetní náročnost, kterou většinou nemám. Navíc celý systém by bylo komplikovanější dotvarovat do potřebné funkcionality - přeci jenom Kodi už je na tento účel přizpůsobeno z výroby.


Závěr

Celý článek pojednává o tom, jak poměrně složitě zprovoznit televizi na televizi. Řeší problém druhé a každé další televize pro službu O2TV. Jak jste jistě v úvodním tónu vycítili, moc se mi to takto nelíbí. Předně nemám rád IPTV, která spotřebovává internetové pásmo, za další se za ní musí platit a pak je tu to hrozné zpoždění



To už je pak jako ten známý vtip o tom, kdo a jak jásá pří vstřelení gólu ve fotbale, podle toho jak se dívá na televizní přenos. Až dosud nejprve jásali diváci analogového vysílání, po nich příjemci digitálního vysílání, a následně diváci IPTV, pak bouchá šampaňské a teprve pak se začínají radovat také diváci satelitní televize.

Ještě jsem neobjasnil, jak je to s tím zdarma. Všechna použitá řešení jsou založena na otevřeném software - tedy nemusí se za ně platit. Notebook či jakýkoliv kus výpočetního železa doma možná najdete také a O2TV není započítaná do nákladů. Protože používáte své přihlašovací údaje, tak se nedopouštíte ani ničeho nezákonného. Paráda, ne?



Pokud jste dočetli až sem, tak vás asi tato problematika zajímá - budu rád, pokud mi do diskuse přidáte svůj pohled na věc nebo svá kritéria a omezení při stavbě podobné soustavy. Jestli jste se jenom zasekli na postupu výše, pokusím se vám s pomoci se zprovozněním. Nejlepší bude, pokud se můžete podělit o zkušenosti s provozováním. 

2016-02-07

Recenze IP kamery IAN 271723 a zkušenosti

Protože si už delší dobu hraji se zabezpečením pomocí internetových kamer, tak jsem si zakoupil v akci v řetězci LIDL inzerovanou neprofesionální IP kameru IAN 271723 za částku 1990 Kč a vrhnul se na prostudování její funkčnosti.



Rovnou zde musím upozornit, že nejde o klasickou IP kameru, protože se chová poněkud netradičně. Předně záznam s ukládá výhradně na microSD kartu. Nenašel jsem stream URL s videem, což je problém, pokud chcete záznam ukládat mimo samotnou kameru, či jej vyhodnocovat analytickým software v reálném čase. 



Z toho také plyne, že samotná kamera nemá webové rozhraní. Obraz můžete kontrolovat výhradně pomocí mobilní aplikace (Android / iOS) nebo windows software, přičemž nastavení lze provádět pouze přes mobil.



Ke kameře se připojuje pomocí čísla DID, což je nějaký pevný unikátní řetězec znaků a pak nastaveným maximálně 10 místným heslem. Do administrace pak potřebujete ještě další heslo. Navazuje se i nějaké TLS spojení, takže přenos hesel je šifrován.



Největší nevýhodu vidím v tom, že kamera nefunguje pouze v lokální síti - ke svému chodu potřebuje internet, neboť po připojení si sice zažádá lokálně přes DHCP o IP adresu, ale poté kontaktuje vzdálený server v internetu (konkrétně Amazon AWS), který slouží jako proxy. 




Ten předává požadavek na přenos obrazu, který kamera multicastuje do koncového zařízení. Hodnocení této vlastnosti záleží na tom, zda jste rozuměli poslední větě. Jestli ne, je to pro vás dobře, kamera funguje i když o tom nic nevíte. Mi se to vůbec nelíbí.

Celkově kamera zatím funguje spolehlivě a je i bytelně vyrobena, bohužel to však není inzerovaná IP kamera, ale nějaký kamerový paskvil - naštěstí "funkční". 

Kompletní manuál i v češtině ke stažení z webu.

Technické parametry: 
  • Typové číslo: IAN 271723 
  • Model: CS12B050150FGF
  • Číslo produktu: 10.023.81 
  • EAN: 8711658461748 
  • Rozlišení obrazu: 1280x720 (HD ready) (720P) 
  • Citlivost 1 až 8 LUX 
  • Síťová rozhraní: Ethernet, WiFi 
  • Fyzická ochrana: IP66 
  • Zabezpečení přístupu: DID username + password

Pozor na umístění kamery a snímáním majetku, protože je to složité ještě z hlediska ochrany osobních údajů. Pokud chcete kameru provozovat na veřejném místě, musíte požádat o povolení Úřad na ochranu osobních údajů, kde dle mého sedí ti největší paranoici v zemi.



Pustil jsem se do analýzy kamery: odposlech paketů a reverzní inženýrství souboru s firmware, který jsem získal od nizozemské podpory. Kamera je ze síťového pohledu klient, nejsou na ní otevřené porty (kromě UDP přenosu obrazu) a tudíž se na ni nedá připojit. 


NEúspěšný pokus o připojení.

Na kameře běží CentOS pro ARM, mám i zdrojáky od kamerového systému "p2pcam" a nevidím v nich žádnou podvratnou činnost, protože pokud někdo cizí kouká na váš obraz, tak to dělá přes server a tam se nedá dostat. Možnost jak ovládnout kameru je připojením USB sériového kabelu, protože na desce uvnitř jsou pro to piny, nicméně se mi to nepovedlo zrealizovat.


Postup rozebrání na videu.


Součásti Camera IAN 271723:
  • wapp-G01SL03C (2014-01-09) modul LED
  • wapp-G01SS02D (2014-10-22) modul kamery
  • wapp-G01SM01C (2013-12-30) základní deska



Z průběžných geekovin: firmware startuje shell na /dev/ttyS0 a root je bez hesla. Podle všeho to vypadá že když vytvoříš na SD kartě txt soubor s názvem jsw_factory_mode.txt, kartu zastrčíš do kamery a kameru zapneš tak by na IP adrese kterou si lízne z DHCP měl poslouchat telnet kterým se lze připojit na roota.

Dále se mi ozval Juha z Finska, že si s kamerou dále hrál: "I decided to improve one camera recording triggering with external PIR sensor. I reverse engineered camera IR LED board and made connection for external trigger."  

Files with board improvement. Dále je tu repozitář, který by mohl pomoci. 

"Camera SW does some unknown heuristics for the original IR signal to decide when to trigger. After some practical tests I found that 25Hz 3-6s burst gives reliable triggering. Please find attached small interface project linking long range PIR sensor and camera. Just simple pulse generator. If needed some filtering for the external PIR can be added."

Pokud máte nějakou další zajímavost či zkušenost s provozováním této kamery, ozvěte se mi do diskuse a přispějte svými postřehy. Komentáře však nejsou fórum pro podporu.

2016-02-03

Riceova věta, triviálnost a vstupně-výstupní vlastnost

Riceova věta ukazuje nerozhodnutelnost celé třídy problémů, její znění je následující "Každá netriviální vstupně/výstupní vlastnost programů je algoritmicky nerozhodnutelná".
Program je v tomto případě tabulka (nekonečná) s dvěma sloupci: v prvním sloupci jsou všechny přípustné vstupy programu a v druhém sloupci je ke každému vstupu uveden buď příslušný výstup nebo nedefinovanost v případě, že výpočet pro vstup neexistuje.


Vstupně-výstupnost

Vlastnost X je vstupně/výstupní právě tehdy, když každé dva programy se stejnou I/O tabulkou (programem) buď oba vlastnost X mají nebo ji oba nemají. Tabulku si představme pro každý Turingův stroj s dvěma sloupci: v prvním sloupci jsou všechny přípustné vstupy programu a v druhém sloupci je ke každému vstupu uveden výstup.

Triviálnost

Každá vlastnost X rozdělí množinu všech Turingových strojů na dvě disjunktní podmnožiny: jedna je množina strojů, které vlastnost X mají, a druhá je množina strojů, které vlastnost X nemají. Z toho lze určit, že:
Vlastnost X je triviální, když je jedna ze dvou zmíněných množin prázdná, tedy buď ji mají všechny stroje mají nebo ji nemá ani jeden. Vlastnost X je netriviální, jestliže ji alespoň jeden stroj má a alespoň jeden stroj nemá. 

Rozhodnutelnost

Každá netriviální vstupně/výstupní vlastnost programů je nerozhodnutelná. Neboli je-li X netriviální vstupně/výstupní vlastností Turingových strojů, pak je příslušný problém nerozhodnutelný podle Riceovy věty. Pozor, negací nezjistíme rozhodnutelnost!

Schéma

Pouze kombinace odpovědí z tabulky dávají smysl:
Vlastnost 1 2 3
Je I/O? A A N
Je triviální? A N N
Je nerozhodnutelná? N A N

Jak na příklady

Pro každé posouzení vlastností se ptám otázkami:
  1. Poznám tuto vlastnost ze vstupně-výstupní tabulky? Pokud ano, tak je vstupně-výstupní.
  2. Existuje program, který tuto vlastnost má a současně jiný program, který ji nemá? Pak není triviální.
  3. Je vlastnost vstupně-výstupní a současně není triviální? Pak je nerozhodnutelná.
Konkrétní příklady jsou ve skriptech Teoretické informatiky na straně 223.

2016-02-02

Redukce bezkontextové gramatiky - postup na příkladu

Dnes chci publikovat obecný algoritmus redukce bezkontextové gramatiky. Je to mimojiné zkoušková úloha předmětu Teoretická informatika na VŠB, přičemž pravděpodobně k ničemu jinému tento postup nepoužijete.

Použité pojmy:

  • X je neterminál
  • Y je neterminál
  • a je terminál
  • | je symbol "nebo"
  • => je symbol "se přepíše na"
  • X => Y | a je pravidlo

Než popíšu svůj postup, dovolím si odkázat na teoretické zdroje: jednak je to přímo prezentace, poté animace redukce a nakonec skripta předmětu (strana 157). Vzhledem k tomu, že je to odtamtud náročné pochopit doporučuji postup níže.

Teoretický postup:

  1. vznikne pomocná množina T z neterminálních symbolů, ze kterých lze odvodit terminální slovo
    • tedy ta písmenka vlevo od šipky, která mají na pravé straně koncový znak (terminál)
  2. do pomocné množiny T přidáme ty neterminály, které lze přepsat na terminály pomocí již přidaných neterminálů.
    • přidávám pouze ta pravidla, ve kterých jsou neterminály samotné s terminály nebo s již přidanými neterminály z množiny T
    • takto postupujeme, dokud už není co přidat
  3. z původního zadání škrtneme ty řádky, které mají na levé straně neterminály, které nejsou v množině T
  4. z původního zadání škrtneme ta pravidla, která v sobě obsahují odstraněné neterminály
  5. vznikne pomocná množina D neterminálů, které jsou dosažitelné z počátečního neterminálu (typicky S)
  6. do pomocné množiny D přidáme ty neterminály, které lze dosáhnout z již přidaných neterminálů
  7. přepsat výslednou redukovanou gramatiku


Praktický postup:

Zadání příkladu: Stručně, ale přesně popište postup redukce gramatiky a přehledně jej aplikujte na zde uvedenou bezkontextovou gramatiku, kde A1 je počáteční neterminál.
 A1 => aA1bA5 | A8A3
 A2 => A4A5 | A5bA2
 A3 => A3aA8b | A8bA6aA6
 A4 => aA2A5 | A5aaA4
 A5 => A1aA4 | bA7A2
 A6 => baA8a | A11abaA1
 A7 => bbA7 | A9bA12
 A8 => A2bA11 | ab
 A9 => bb | aA12b
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9

Krok 1. najít terminály
A8 => ab
A9 => bb
do pomocné množiny si přidám neterminály A8 a A9
T = {A8, A9}
Krok 2.1 dokud přibývají další, tak najít další pravidla, která obsahují samostatné terminály z množiny T. Prohledávám:

A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A3 => A3aA8b | A8bA6aA6
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
T = {A8, A9} U {A6, A12}

Krok 2.2 prohledávám:
A1 => aA1bA5 | A8A3 
A2 => A4A5 | A5bA2 
A3 => A3aA8b | A8bA6aA6
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A7 => bbA7 | A9bA12
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
T = {A6, A8, A9, A12} U {A3, A7} 

Krok 2.3 prohledávám
A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A10 => A1abA4 | bA10b 
A11 => A1bbA6 | A3bA8
T = {A3, A6, A7, A8, A9, A12} U {A1, A11} 

Krok 2.4 prohledávám
A2 => A4A5 | A5bA2 
A4 => aA2A5 | A5aaA4 
A5 => A1aA4 | bA7A2 
A10 => A1abA4 | bA10b 
T = {A1, A3, A6, A7, A8, A9, A11, A12} U {} 
konec prohledávání

Krok 3 vypuštění neterminálních stavů z původního zadaní (A2, A4, A5, A10), zbyde:
A1 => aA1bA5 | A8A3 
A3 => A3aA8b | A8bA6aA6 
A6 => baA8a | A11abaA1 
A7 => bbA7 | A9bA12 
A8 => A2bA11 | ab 
A9 => bb | aA12b 
A11 => A1bbA6 | A3bA8 
A12 => aA1bA12a | aA9

Krok 4 vyřazení pravidel, která v sobě obsahují vyřazené neterminály (A2, A4, A5, A10), zbyde:
A1 => A8A3 
A3 => A3aA8b | A8bA6aA6 
A6 => baA8a | A11abaA1 
A7 => bbA7 | A9bA12 
A8 => ab 
A9 => bb | aA12b 
A11 => A1bbA6 | A3bA8 
A12 => aA1bA12a | aA9

Krok 5 ověření dosažitelnosti již redukovaných pravidel. Do množiny D vždy patří startovací neterminál
D = {A1}

Krok 6.1 z A1 se dá dostat do A3 a A8, přidám si je do seznamu, zbývá
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
 
D = {A1} U {A3, A8}

Krok 6.2 je vhodné postupovat rozborem neterminálu A3, zbývá
A3 => A3aA8b | A8bA6aA6 
A6 => baA8a | A11abaA1 
A7 => bbA7 | A9bA12 
A8 => ab 
A9 => bb | aA12b 
A11 => A1bbA6 | A3bA8 
A12 => aA1bA12a | aA9 
D = {A1, A3} U {A8, A6}

Krok 6.3 je vhodné postupovat rozborem neterminálu A6, zbývá
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
 
D = {A1, A3, A6} U {A8, A11}

Krok 6.4 je vhodné postupovat rozborem neterminálu A8, zbývá
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
 
D = {A1, A3, A6, A8} U {A11}

Krok 6.5 je vhodné postupovat rozborem neterminálu A11, zbývá
A7 => bbA7 | A9bA12
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
 
D = {A1, A3, A6, A8, A11} U {}

Krok 7 z gramatiky jsme vyřadili pravidla:
A7 => bbA7 | A9bA12 
A9 => bb | aA12b 
A12 => aA1bA12a | aA9

Krok 7.1 zbývá gramatiku přepsat do redukovaného tvaru, toto je výsledek:
A1 => A8A3
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A8 => ab
A11 => A1bbA6 | A3bA8
Tím jsme docílili výsledné redukované gramatiky. Je velmi lehké udělat v tomto postupu chybu, odměnou za splnění je obvykle 8 bodů.

K procvičení zde mám i další příklad, tentokráte popsaný výrazně méně: Zadání:
A => FaG | BA
B => IH | aaI
C => ε | aGD
D => aELI | AAH
E => AGF | AA
F => KC | DJa
G => aaaF | bGa
H => IBa | BIH
I => IaI | DH
J => IH | CKFaE | JH
K => ab | ba
L => bLa | Ka
První pomocná množina:
T = {C, K} U {F, L} U {G} U {A} U {E} U {J} U {} = {A, C, E, F, G, J, K, L} 
vyřazeno = {B, D, H, I}
Zbývající gramatika:
A => FaG
C => ε
E => AGF | AA
F => KC
G => aaaF | bGa
J => CKFaE
K => ab | ba
L => bLa | Ka
 
D = {A} U {F, G} U {K, C} U {} = {A, C, F, G, K}
Výsledek
A => FaG
C => ε
F => KC
G => aaaF | bGa
K => ab | ba
Pokud si nejste postupem jistí, zkuste ještě jednou prostudovat oficiální animaci. Poznámka: Všimněme si, že metoda redukce gramatiky nijak nezajišťuje, že výsledná gramatika je nejmenší možná pro daný jazyk, či něco takového. Je to zde jinak než u konečných automatů; neexistuje totiž algoritmus, který by k dané bezkontextové gramatice zkonstruoval nejmenší s ní ekvivalentní.

2016-01-25

Chomského normální forma bezkontextových gramatik - referát

Do předmětu Teoretická informatika oboru Informační a komunikační technologie na VŠB jsem měl za úkol zpracovat krátký referát na téma Chomského normální forma bezkontextových gramatik. Nejde o žádnou vědeckou práci, ale i tak je mi líto nechat tento text ležet v šuplíku bez užitku někomu dalšímu. Celý text ke stažení.

Chomského normální forma je tvar či specifický způsob zápisu formální gramatikyPři převodu bezkontextové gramatiky do Chomského normální formy se po odstranění pravidel typu A → ε provádí krok, který odstraňuje pravidla typu X → Y (neterminál se přepisuje na neterminál). (Pak dostaneme jen pravidla typu A → α, kde α je terminál nebo |α| ≥ 2, přičemž generovaný jazyk se nezměnil.)


Noan Chomsky - filosof a matematik

Zadání

Na vhodném příkladu ilustrujte algoritmus odstraňující ona pravidla X → Y a ukažte jeho korektnost.

Definice

Je přímo uvedena výše, jinými slovy: Bezkontextová gramatika je v Chomského normální formě, jestliže každé její pravidlo je tvaru X → Y Z nebo X → a, kde „X, Y, Z“ označují neterminální symboly a „a“ terminální symbol. Tedy na levé straně je jeden neterminál, na pravé terminál nebo maximálně 2 další neterminály. Kde A, B a C jsou neterminály, α je terminál, S je startovní neterminál a ε je prázdný řetězec, přičemž B ani C nemohou být startovacím neterminálem.

Tvar CHNF

  • A → BC nebo
  • A → α nebo
  • S → ε (je povoleno, pokud gramatika generuje prázdný řetězec a zároveň se S nevyskytuje na pravé straně žádného pravidla)

Algoritmus

  1. odstranění ε pravidel;
    • nahrazení těmi terminály a neterminály, které by se tam mohly objevit a přidat je za stávající pravidla. Je třeba to provést důkladně a zahrnou všechny možné vzniknuvší kombinace!
  2. odstranění jednoduchých pravidel;
    • samostatné neterminály v jednom znaku nahradit jejich přepisem
  3. odstranění terminálů mimo A → α;
    • zavést substituci novým neterminálem za všechny terminály, které jsou součástí neterminálů, kromě osamocených terminálů nebo skupiny terminálů.
  4. pohlcování neterminálních symbolů.
    • Všechny neterminály, které jsou delší než 2 znaky se musí zkrátit zavedením dalších substitucí. Ponechá se první znak a zbývající se substituují dalším neterminálem.
  5. Výsledkem je sada pravidel ve tvaru X → Y Z, přičemž pro zjednodušení mohou být zapsána i za sebou se znakem „nebo |“.

Příklady


Použití

Bezkontextové gramatiky
G = ({VÝROK, PŘÍVLASTEK, PODMĚT, PŘÍSUDEK}, {malý, velký, pes, kocour, běží, leží, spí}, VÝROK, Pdále)

Význam

Pro pochopení formy je třeba mít představu o tom, čeho forma to je. S bezkontextovými jazyky a gramatikami se hojně setkáváme při syntaktické analýze textu, třeba zdrojových kódů programovacích jazyků. Slovo „bezkontextová“ v názvu gramatiky znamená, že na levé straně každého pravidla stojí jeden neterminál bez sousedních symbolů (tedy není v „kontextu“).

Všechny bezkontextové jazyky lze generovat bezkontextovými gramatikami v jistém speciálním tvaru. Derivační stromy, příslušné k těmto gramatikám, pak mají jednotný tvar. Tato skutečnost usnadňuje cestu k závěrům v některých úvahách o bezkontextových jazycích. Příkladem je Chomského nebo Greibachova normalní forma.

Převedení zápisu gramatiky do CHNF vede k vytvoření jednoznačného derivačního stromu. Gramatika G je jednoznačná, jestliže každé slovo z L(G) má právě jedno levé odvození (právě jeden derivační strom), jinak je víceznačná a jako takovou ji není možné vždy transformovat na ekvivalentní jednoznačnou gramatiku.

Hlavní výhodou v Chomského normální formě je že, každé odvození řetězce s n písmeny má přesně 2n - 1 kroků, je tedy možné určit, zda je řetězec v jazyku všech derivací ve známém počtu operací.


Derivační strom

Derivační strom je v reprezentant syntaktické struktury slovního řetězce podle formální gramatiky. V derivačním stromě jsou vnitřní uzly označeny jako neterminály gramatiky, zatímco koncové uzly jsou označeny jako terminály. Derivační stromy mohou být využity pro generování nebo analýzu vět v přirozeném jazyce, stejně tak jako během zpracování počítačových jazyků.

Vytváření derivačních stromů ze specificky formátované gramatiky vede na jednoznačné derivační stromy, což je velký výhoda pro porovnávání bezkontextových gramatik mezi sebou.

Důkaz

Nejprve věta 12.2.2 o odstranitelnosti ε přechodů: Ke každé bezkontextové gramatice G lze sestrojit ekvivalentní nevypouštějící gramatiku G‘ tž. L(G‘) = L(G) − {ε}. Důkaz ve skriptech str. 62.


Co se tím říká? Nedochází k porušení správnosti gramatiky, neboť důkaz odstranění ε přechodů se provádí výše, to je první zásah do konstrukce gramatiky: ve stručnosti se pouze přepisují symboly na nová umístění, ale jde jen komplikaci zápisu. Dalším porušením integrity by mohlo být přepisování pravidel neterminály, ale lze jistě souhlasit, že zavedením substituce nedochází ke změně významu původního výrazu a právě tato úprava se v průběhu převodu do CHNF odehrává. Intuitivně lze vyčíst, že v rámci algoritmu nedochází k modifikaci samotné gramatiky.

Jednoduše si lze představit důkaz jako problém grafu o 2 uzlech nad sebou. Pokud horní a spodní uzel rozdělím a vložím mězi ně uzel další, pak se zcela logicky nemění význam grafu, pouze je v něm více uzlů. Přesně stejný případ vytváří gramatika v Chomského normální formě, protože nemění význam a pouze dochází k přidání pravidel se specifickými vlastnostmi.

Zdroje