Hua Nam Son, Gubán Ákos

Számítástudomány


5.10. Ellenőrző kérdések és feladatok

  1. Legyen . Az alábbi szavak közül melyik az -nak
    1. részszava?
    2. tükörképe?
  2. Igaz-e az állítás? Ha az -nak egyik részszava, akkor az -nek egyik részszava.
     
  3. Adjuk meg reguláris kifejezéssel azt a {0,1} ábécé feletti nyelvet, amely azon szavakból áll, amelyek
    1. tartalmazzák részszóként az 001 szót!
    2. tartalmazzák részszóként az 01 vagy 11 szót!
    3. a 01 és 11 szóval végződnek!
    4. nem tartalmazzák részszóként a 01 szót!
     
  4. Legyen . Az alábbi szavak közül melyik tartozik -be?
    = 101100,
    = 11001010110,
    = 01010111.
     
  5. Legyen Az alábbi szavak közül melyik tartozik -be?
     
    = 01100,
    = 1100101010,
    = 01010111.
  6. Legyen egy véges automata, ahol
    • a bemenő ábécé,
    • az állapothalmaz, ahol , a kezdő-, illetve végállapot,
    • az alábbi állapot átmeneti függvénye:
     
     
    1. Igaz-e, hogy ?
    2. Igaz-e, hogy ?
    3. Írja ki azt a reguláris kifejezést, amely reprezentálja -t.
  7. Írjunk ki egy véges determinisztikus automatát, amely -t ismeri fel, ha:
     
  8. Egy nyelvtan egyik szabálya . Milyen típusú lehet a nyelvtan?
     
  9. Legyen egy generatív rendszer, ahol:
     
    Ellenőrizzük, hogy az alábbi állítások közül melyik igaz:
    1. -nek egyik közvetlen levezetése.
    2. -nek egyik levezetése.
    3. -nek egyik levezetése.
     
  10. Írjunk ki olyan környezetfüggetlen nyelvtant, amely az nyelvet generálja!
  11. Konstruáljunk olyan peremautomatát, amely az nyelvet ismeri fel! Becsüljük meg a felismerési folyamat időbonyolultságát!
     
  12. Legyen
    1. Igaz-e, hogy egy környezetfüggetlen nyelv?
    2. Konstruáljunk egy olyan Turing-gépet, amely a problémát dönti el! Becsüljük meg a döntési folyamat időbonyolultságát!
    3. Konstruáljunk egy olyan kétszalagos Turing-gépet, amely a problémát dönti el!

Számítástudomány

Tartalomjegyzék


Kiadó: Akadémiai Kiadó

Online megjelenés éve: 2018

ISBN: 978 963 454 217 9

A BGE Gazdaságinformatikus szak egyik legfontosabb alapozó tantárgya a Számítástudomány, amely bevezetést nyújt a matematikai logika és a formális nyelvek elméletébe, az automataelméletbe, valamint a programozás alapjaiba. A tárgyat több mint hat éve oktatjuk, és szükség volt egy olyan átfogó oktatási anyagra, mely a tárgy megértéséhez nyújt segítséget a hallgatók számára. A könyv felépítése jól körülhatárolja a témákat, valamint mintapéldák segítségével javítja az elméleti anyagok gyakorlatba történő leképezését.

A szerzők elsősorban informatikai és közgazdasági ismeretekkel rendelkező hallgatók számára nyújtanak betekintést a Számítástudomány eszközeiről, módszereiről és módszertanairól. Elsősorban Gazdaságinformatikus hallgatók számára készült a könyv, de olvasása hasznos lehet Gazdálkodás és menedzsment, valamint Pénzügy és számvitel szakos hallgatók számára is. Kiegészítő információkat tartalmaz a mélyebb matematikai alapokkal nem rendelkező hallgatók számára az informatikai elveket biztosító matematikai elméletek megismertetésében. Szemléletében műszaki-matematikai vonalat követ, ezáltal komplexebb rálátást nyújt az IT elveinek szélesebb körű megismeréséhez. Sok sikert és élvezetes tanulmányozást kívánunk!

A szerzők

Hivatkozás: https://mersz.hu/hua-guban-szamitastudomany//

BibTeXEndNoteMendeleyZotero

Kivonat
fullscreenclose
printsave