Git Product home page Git Product logo

filippodaniotti / appunti-lfc Goto Github PK

View Code? Open in Web Editor NEW
33.0 2.0 10.0 8.49 MB

Appunti di Linguaggi Formali e Compilatori - Prof.ssa P. Quaglia - Università di Trento

License: GNU General Public License v3.0

TeX 97.53% Lex 0.79% Yacc 1.27% Python 0.16% Roff 0.01% Batchfile 0.08% Dockerfile 0.07% Shell 0.10%
latex latex-document formal-languages compiler universit-di-trento university appunti appunti-lfc linguaggi-formali compilatori

appunti-lfc's Introduction

Hi!

telegram gmail linkedin

About me

Projects

Machine learning

Signal processing

System programming

Full stack

Notes and study materials

appunti-lfc's People

Contributors

bigemperor26 avatar civts avatar euberdeveloper avatar fedeizzo avatar filippodaniotti avatar francescobozzo avatar samaretas avatar simone-alghisi avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

appunti-lfc's Issues

Ricreare gli alberi di if-else in LaTeX

Queste due figure dovrebbero essere ricreate in LaTeX con dei pacchetti appositi (forse forest può essere il pacchetto giusto, ma non ci metterei la mano sul fuoco)
dangling_else_1
dangling_else_2

\begin{figure}
\centering
\includegraphics[width=.7\textwidth,keepaspectratio]{dangling_else_1.jpg}
\caption{Primo albero di derivazione per Eq. \ref{dangling_else}}
\label{dangling_else_1}
\end{figure}
\begin{figure}
\centering
\includegraphics[width=.7\textwidth,keepaspectratio]{dangling_else_2.jpg}
\caption{Secondo albero di derivazione per Eq. \ref{dangling_else}}
\label{dangling_else_2}
\end{figure}

Capitolo 8 pagina 170

Nell'ultimo passaggio dell'algoritmo shift reduce manca la S nel symSt dopo aver effettuato la riduzione S -> aABe
Schermata 2021-01-02 alle 14 48 08

Labels refactoring

L'idea è di utilizzare convenzioni molto forti sulla definizione e uso delle labels.

In particolare, vorrei che le labels fossero assegnate a:

  • ogni asset importato nel documento;
  • tutte le equazioni non anonime;
  • tutti quei marker di sezione che lo dovessero richiedere.

Ogni label dovrà avere il seguente formato \label{type:file-name}, dove:

  • type (tutto in minuscolo) indica il "tipo" dell'elemento cui la label è assegnata, quali ad esempio: fig, alg, tab, eq, subsec, etc;
  • file-name è il nome dell'asset, se l'elemento è un asset;
  • il formato per gli elementi che non sono asset verrà specificato a breve.

Nel testo si dovranno usare le labels nel seguente formato Type.\ref{label}, con il tipo di elemento capitalized.

Bisogna spiegarlo

Bisogna spiegarlo
image

\begin{figure}[H]
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_a.tex}
\subcaption{step by step by mike by bisognaspiegarlo}
\label{pl-es4-sbs_1}
\end{minipage}
\hfill
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_b.tex}
\subcaption{step by step by mike by bisognaspiegarlo 2}
\label{pl-es4-sbs_2}
\end{minipage}
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_c.tex}
\subcaption{step by step by mike by bisognaspiegarlo 3}
\label{pl-es4-sbs_3}
\end{minipage}
\hfill
\begin{minipage}[b]{0.4\textwidth}
\centering
\subimport{assets/figures/}{regual_recognition_es4-2_d.tex}
\subcaption{step by step by mike by bisognaspiegarlo 4}
\label{pl-es4-sbs_4}
\end{minipage}
\caption{}
\end{figure}

Assets names refactoring

Vorrei stabilire delle convevnzioni abbastanza forti sui nomi dei file degli assets.

Al momento non ho ancora idee precise, se non che vorrei utilizzare solamente lettere minuscole, dashes e underscores.

Refactoring stile tabelle

Alcune tabelle sarebbero molto più chiare se aggiungessimo delle vertical rules, come ad esempio le seguenti, riguardanti gli esercizi sulla subset construction.
novrule
vruled

Revisionare lec-05

È la sezione sugli esercizi di applicazione del pumping lemma for free languages e attualmente è un po' un blocco di testo monolitico, e manca in generale di un po' di dettaglio.

\subsection{Applicazioni}
Qui passiamo alle applicazioni del \emph{Pumping Lemma}. In particolare può essere utilizzato per provare che un linguaggio \(\mathcal{L}\) non è libero.
In generale, da un'implicazione logica del tipo \(A \implies B\), è possibile ottenere la negazione \(\neg A \implies \neg B\). Nel nostro caso, da \(\mathcal{L}\) libero \(\implies\) Tesi del \emph{Pumping Lemma}, abbiamo \(Not\) tesi del \emph{Pumping Lemma} \(\implies\) \(\mathcal{L}\) \(Not\) libero.
La negazione della tesi del \emph{Pumping Lemma} è la seguente:
\begin{itemize}
\item \(\forall p \in \mathbb{N}^+\) tale che
\item \(\exists z \in \mathcal{L} : |z| > p\), allora
\item \(\forall u, v, w, x, y\) tale che:
\begin{itemize}
\item \(z = uvwxy \textrm{ } \land\)
\item \(|vwx| \leq p \textrm{ } \land\)
\item \(|vx| > 0 \textrm{ }\land\)
\item \(\exists i \in \mathbb{N}.uv^iwx^iy \not\in \mathcal{L}\)
\end{itemize}
\end{itemize}
Lasciamo al lettore immaginare gli altri modi in cui è possibile riscrivere la negazione della tesi del \emph{Pumping Lemma} applicando le basi di algebra booleana.
Passiamo dunque ad esempi pratici.
ES 1
Sia \(\mathcal{G}\) così definito
\(S \rightarrow aSb \ abc\)
\(cB \rightarrow Bc\)
\(bB \rightarrow bb\)
ci chiediamo dunque se \(\mathcal{G}\) è \emph{context dependent} o \emph{free}. Ovviamente è \emph{context dependent}.
Ci chiediamo quale sia il linguaggio generato da \(\mathcal{G}\), \(\mathcal{L(G)}\) ed è \({a^n b^n b^n | n>0}\)
Ci chiediamo infine se il linguaggio \(\mathcal{L(G)}\) sia o meno un linguaggio libero. Per farlo possiamo semplicemente utilizzare la negazione del \emph{Pumping Lemma} per dimostrare che \(\mathcal{L(G)}\) non è libero.
Sia \( p \in N^+\) un numero intero arbitrario
Possiamo prendere un numero \(z=a^pb^pc^p \in \mathcal{L}\) che soddisfa la condizione \(|z|\leq p\)
Quindi possiamo prendere qualsiasi decomposizione di \(z = uvwxy, |vwx|\leq p |vx|>0\).
Sappiamo che la parola \(z\) è composta in questo modo. \(\underbrace{aa...a}_\text{\emph{p}}\underbrace{bb...b}_\text{\emph{p}}\underbrace{cc...c}_\text{\emph{p}}\).
La sottostringa \(vwx\) deve essere sicuramente in una di queste possibili posizioni
\(a\underbrace{a...a}_\text{\emph{vwx}}
a\underbrace{a...abb...b}_\text{\emph{vwx}}
b\underbrace{b...b}_\text{\emph{vwx}}
b\underbrace{b...bc...c}_\text{\emph{vwx}}
c\underbrace{c...c}_\text{\emph{vwx}}c\)
da cui abbiamo che qualsiasi sia la posizione di \(vwx\) all'interno della parola \(z\) è possibile costruire una parola con un numero non bilanciato di \(a,b,c\) semplicemente ponendo \(v^i,x^i,i=0\)
Dunque troviamo una parola che non appartiene al linguaggio. Se il linguaggio fosse libero, tutte le parole costruite in questa maniera dovrebbero appartenere al linguaggio. Dunque il linguaggio non è
\emph{free}
Passiamo dunque ad un altro esempio riprendendo l'esercizio lasciato per casa a suo tempo
ES 2
\(S \rightarrow CD \)
\(C \rightarrow aCA | bCB \)
\(AD \rightarrow aD \)
\(BD \rightarrow bD \)
\(Aa \rightarrow aA \)
\(Ab \rightarrow bA \)
\(Ba \rightarrow aB \)
\(Bb \rightarrow bB \)
\(C \rightarrow \epsilon \)
\(D \rightarrow \epsilon \)
Si verifica facilmente che il linguaggio generato da tale grammatica è \(\mathcal{L(G)} =\{ww | w\in\{a,b\}^*\}\)
Ci chiediamo allore se tale linguaggio sia libero o meno
Un lettore naive potrebbe essere portato ad applicare la proprietà di chiusura dei linguaggi liberi rispetto alla operazione di concatenazione per dimostrare che suddetto linguaggio sia libero, in quanto sappiamo che \(\mathcal{L'(G)} =\{w | w\in\{a,b\}^*\}\) è un linguaggio libero. Tuttavia l'operazione di concatenazione non rispetta la proprietà di palindromia di \(\mathcal{L}\).
È infatti semplice provare che \(\mathcal{L}\) non è libero
DIM
Sia \(\mathcal{L}\) libero
sia \(z=a^pb^pa^pb^p, z\in \mathcal{L}, z=uvwxy, |vwx|\leq p \)
Per esempio supponiamo sia \(|vwx|=b^p\), allora ic è facile prendere \(uv^0wx^0y\) e verificare che questo non può avere la forma \(a^pb^pa^pb^p\)
Dunque abbiamo trovato un elemento che contraddice il \emph{Pumping Lemma} e dunque l'ipotesi iniziale non è valida, ovvero \(\mathcal{L}\) non è \emph{free}

Automa production wrong

Figure 8.5 (Figura 8.5: Automa Caratteristico per la Bottom-Up Parsing Table) on page 158 has b transiction from state 3 to state 7. This is wrong. In the original automa the transition is trought d.

Revisione capitoli 1 e 2

La formattazione attuale fa schifo, c'è l'identazione di paragrafo senza separazione del testo praticamente ogni due righe.

  • Capitolo 1
  • Capitolo 2

Typo capitolo 8

Lista dei typo trovati durante la lettura del capitolo 8 (post-refactoring):

  1. riga 10 pagina 142 "la andremo ..."
  2. penultima riga pagina 144 "per fare in questo"
  3. ultima riga prima dello pseudocodice pagina 146 "due volte di fila due punti"
  4. punto 1 pagina 147 "calcoliamo il la chiusura"
  5. riga 5 pagina 149 "gli stessi item; in questo casp"
  6. riga 4 sezione 8.4 pagina 159 "l'algoritmo di s/r viene uisto"
  7. nota 5 pagina 163 interrotta sul piu' bello per poi tornare nella pagina dopo
  8. nota 6 pagina 169 "meglio tenere la conscienza"
  9. nota 7 pagina 170 "QUesta frase"

Risoluzione labels per gli pseudocodici

Gli pseudocodici non hanno alcuna label assegnata e, di conseguenza, non è possibile referenziarli attraverso il consueto comando \ref{<label>}.
Inoltre, il pacchetto algorithm2e prevede la possibilità di fare riferimenti alle righe stesse, per cui si potrebbe considerare di implementare anche questa funzionalità.

Errore formattazione esercizio 3.4

Nell'esercizio 4 alla fine del terzo capitolo c'e' un errore nella consegna:
scrot-2020-12-18_15:33:14
L'ultima k di entrambi i linguaggi dovrebbe stare all'esponente di c assieme al 2

Utilizzo di \emph{}

Dobbiamo decidere una prassi comune per l'utilizzo del comande \emph{} e in base a tale decisione ristrutturare l'intera dispensa.
Al momento l'utilizzo di tale comando è abbastanza randomico.

[Enhancement] Includere PDF nella repo

Per quanto il source sia importante e fondamentale non mi è chiara la scelta di non includere direttamente un pdf compilato all'interno della stessa repo.

Consiglio di settare una action in modo che il pdf sia automaticamente ricompilato ad ogni cambiamento

Edit, ho notato solo ora che la action è già settata ma non vi è alcun pdf in /src :(

Fix Fig 1.5

Nel test si dice che la Fig. 1.5 contiene il parse tree sulla destra mentre il codice intermedio sulla sinistra, tuttavia viene visualizzato solo il parse tree. Ho dato un occhiata al sorgente e sembra ok (?)
Schermata 2020-10-30 alle 16 18 42

Errore Tabella 10.1

Nella tabella mancano le seguenti entry:

  • Tab[7,digit]=s6
  • Tab[7,F]=4
    Che corrispondono agli archi colorati in rosso in figura
    immagine

Appendice A: Foglio di esercizi 1

La professoressa ha rilasciato un foglio di esercizi simili a quelli che potremmo trovare nella prima parte dell'esame; sarebbe interessante svolgerli per bene, descriverne dettagliatamente il procedimento e presentarlo in un'appendice a fine testo.

  • Risoluzione degli esercizi su supporti meno raffinati di LaTeX
  • Impaginazione LaTeX

Labels refactoring

Servirebbe fare un bel refactoring delle labels, stabilendo delle convenzioni moderatamente forti sia su:

  • formato: come devo chiamare la label che si riferisce al terzo esercizio sull'applicazione della subset construction? sc-es-3? sc_ex_3?
  • utilizzo: quali sono le situazioni in cui è opportuno usare references alle labels? Potremmo ad esempio pensare di utilizzarle sempre per riferirci alle immagini, data l'imprevedibilità del comportamento di LaTeX con il loro posizionamento nel testo.

Error in example

image

In questo caso, se io avessi "abababab", alla fine otterrei una pila vuota, quindi il procedimento "passerebbe", anche se la parola non appartiene al linguaggio (a^n)(b^n). Può essere che mi sbagli, ma il procedimento dia sempre dei negativi giusti, ma che abbia dei falsi positivi.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.