This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
These notes are low-effort, due to catching up in this module. See the videos and slides for more detail. Congestion Congestion is where too many sources are sending too much data too fast for the network to handle. This can give: Long Delays Packet Loss This is different from flow...
These notes are low-effort, due to catching up in this module. See the videos and slides for more detail. TCP Flow Control This is where the receiver sends messages to the sender to slow the rate of transfer. This is so that the incoming data doesn’t overflow the buffer by...
To complete this algorithm the grammar must be in Chomsky Normal Form, including no $\epsilon$ or unit productions. Method This method uses a table like so: $1k$ $\vdots$ $\vdots$ 12 23 11 22 $kk$ $x_1$ $x_2$ $\cdots$ $x_k$ Where $x_k$ is a...
To parse quicker we can use the Cocke-Younger-Kasami algorithm. To do this we must prepare the CFG and convert it to Chomsky normal form: Eliminate $\epsilon$ productions. Eliminate unit productions. Add rules for terminals and split longer sequences of non-terminals. Chomsky Normal Form A CFG is in Chomsky normal form...
Parsing We can use a brute force method like BFS to search if an input is in the language. This is not ideal as it produces an exponentially large tree. If input is not in the language parsing will never stop. When to Stop We could try to aid the previous...
As there could be more than one parse tree from a given input this can cause issues when trying to define the meaning of a string. Ambiguity A CFG is ambiguous if some string has more than one parse tree. Is $S\rightarrow SS\vert x$ ambiguous? Yes as you could make...
Every regular language is context free. Not all context free languages are regular. Regular to Context-Free Conversion Regular Expression Context Free Grammar $\emptyset$ Grammar with no rules. $\epsilon$ $S\rightarrow\epsilon$ $a$ (alphabet symbol) $S\rightarrow a$ $E_1+E_2$ $S\rightarrow S_1\vert S_2$ $E_1E_2$ $S\rightarrow S_1S_2$ $E_1^*$ $S\rightarrow SS_1\vert\epsilon$ $S$ becomes that net start symbol....
For examples of many context free grammars see this lecture Definition A context-free grammar is given by ($V,\Sigma,R,S$) where: $V$ - Finite set of variables or non-terminals. $\Sigma$ - Finite set of terminals. $R$ - A set of productions or substitution rules of the form: \[A\rightarrow\alpha\] where $A$ is a...
For a large project, why is a detailed software design important? A detailed software design is made for the developers to help them in implementing the software. This is important as in a system with that many sub-systems and components there needs to be strict requirements concerning the communication between...
These are architectural designs for software the executes on more than one processor. This can be on the same computer or between many machines. System Types Personal Systems - Not distributed and are designed to run on a personal computer. Embedded Systems - Run on a single processor or on...