3.3. Algorytmy parsingu Problem rozbioru gramatycznego jest próbą odpowiedzi na pytanie: czy dany ciąg symboli terminalnych jest słowem należącym do języka L(G) generowanego przez daną gramatykę. Aby odpowiedzieć na to pytanie stosujemy jeden z dwóch algorytmów: a) algorytm wyprowadzający „top-...
ANALIZA SCHEMATÓW BLOKOWYCH OPIS UKŁADÓW ZA POMOCĄ ZMIENNYCH STANU Zadanie 1 (Zmienne stanów i schematy blokowe układów) Problem: Wyznaczyć transmitancję od u do y układu: Rozwiązanie: 1) Przesuwamy węzeł za blok G2: 2) Łączymy szer...
3.5. Automat ze stosem A = T – zbiór symboli terminalnych Q – zbiór stanów #Q T = { 0, 1} G = ∈ GBK Q = { q0, q1, q2}; F = {q0} N = {Z} q0 – stan początkowy T = { 0 , 1} S ...
3.2. Drzewa rozbioru syntaktycznego Drzewo rozbioru syntaktycznego według gramatyki G = ∈GBK jest to drzewo zorientowane z korzeniem k0 i funkcją etykietującą wierzchołki f: K!M, jeśli spełnione są następujące warunki: k0 (1) M ⊆ (N ∪ T) ∪{ε} (2) f(k0) = Z ... kn k2 k1 (3) niech k1,...,k...
1.4. Grafy, drzewa Graf zorientowany Graf zorientowany jest parą gdzie: K - skończony, niepusty zbiór wierzchołków D ⊆ K × K - zbiór krawędzi Funkcje etykietujące f: K ! MK - przypisuje etykietę (nazwę) każdemu wierzchołkowi g: D ! MD - przypisuje etykietę (nazwę) każdej krawędzi Inne d...
2.2. Gramatyki, wyprowadzenia Gramatyka Gramatyką G nazywamy czwórkę uporządkowaną G = gdzie: N – zbiór symboli nieterminalnych, T – zbiór symboli terminalnych, P –...
4.6. Gramatyki regularne G = jest gramatyką prawostronnie liniową, jeśli jej produkcje mają postać: (i )U → xV * x∈T U,V∈N (ii )U → x G = jest gramatyką prawostronnie regularną, jeśli jej produkcje mają postać : (i )U → aV a∈T U,V∈N (ii )U → a oraz (iii) jeśli (Z→ε)∈P to Z n...
2. Języki, gramatyki 2.1. Języki Definicja języka Niech T będzie alfabetem, T* - zbiorem wszystkich łańcuchów nad alfabetem T. Dowolny podzbiór L zbioru T* nazywamy językiem L nad alfabetem T. L ⊆ T* Przykłady: L0 = Ø - język pusty L1 = {ε} - język zawierający tylko słowo puste * L2 = T...
4.3. Przekształcenia automatów skończonych Konstrukcja automatu skończonego (niedeterministycznego) na podstawie wyrażenia regularnego (algorytm Thompsona). Wejście: wyrażenie regularne r nad alfabetem T Wyjście :
3.4. Przekształcenia gramatyk bezkontekstowych Definicje Niech będzie dana gramatyka bezkontekstowa G = ∈ GBK Symbol X ∈ (N∪T) nazywamy nieużytecznym w G∈GBK jeśli nie można w tej gramatyce przeprowadzić wyprowadzenia: Z ⇒*G ...
