วีดีโอ

Turing machines (Part 2): Working example

Turing machines (Part 1): Introduction to TM, Formal definition

This video shows how to obtain a Pushdown automaton (PDA) from a given Context-free Grammar (CFG).

This video presents in an easy and simple way Pushdown automata (PDA) and shows how PDA are able to recognize context-free languages (CFL). Pushdown automata (PDA) are like nondeterministic finite automata but they have the possibility to use a stack as an auxiliary memory.

This video explains in a simple and clear way the concept of ambiguity in context-free languages (CFL). Ambiguity in context free languages refers to the possibility of having an input string that may be interpreted in different ways. The video defines: -Ambiguous string -Ambiguous CFG (Context-Free Grammar) -Ambiguous Language Some examples where ambiguity is encountered are discussed at the e...

This video shows in an easy and simple way how to write context-free grammars for regular languages. Context-free languages are the languages described by context-free grammars (CFG). A language is regular if an only if there's a Finite State Machine (FSM) that recognizes it. We will show that regular languages are a subset of context-free languages since we can obtain a context-free grammars (...

This video is one of a playlist which presents some examples of context-free grammars (CFG). We'll show how to reason in order to find a context-free grammar (CFG) for a given language. After defining a grammar for the language, we'll show how to prove that a string is accepted. The language discussed in this video is the set of strings s over the alphabet {a,b}, where s=a^nb^mc^{n m}. An examp...

This video is one of a playlist which presents some examples of context-free grammars (CFG). We'll show how to reason in order to find a context-free grammar (CFG) for a given language. After defining a grammar for the language, we'll show how to prove that a string is accepted. The language discussed in this video is the set of strings s over the alphabet {a,b}, where s=a^nb^m, m greater than ...

This video is one of a playlist which presents some examples of context-free grammars (CFG). We'll show how to reason in order to find a context-free grammar (CFG) for a given language. After defining a grammar for the language, we'll show how to prove that a string is accepted. The language discussed in this video is the set of strings over the alphabet {a,b}, where the string is not in the fo...

This video is one of a playlist which presents some examples of context-free grammars (CFG). We'll show how to reason in order to find a context-free grammar (CFG) for a given language. After defining a grammar for the language, we'll show how to prove that a string is accepted. The language discussed in this video is the set of strings over the alphabet {a,b}, where the number of a's is greate...

This video is the first one in a playlist which presents some examples of context-free grammars (CFG). We'll show how to reason in order to find a context-free grammar (CFG) for a given language. After defining a grammar for the language, we'll show how to prove that a string is accepted. An example of string is shown accepted by use of derivation. Another example of string is shown correct by ...

This video presents in an easy and simple way the context-free languages. Context-free languages are the languages described by context-free grammars (CFG). Context-free grammars are explained with a very simple example of language, then defined, then discussed with a more elaborate example. A grammar is a set of rules used for substitution, known also as productions. It defines a set of non-te...

Pumping Lemma is used to prove that a language is not regular. Pumping Lemma for regular languages: A property of regular languages states that to accept long strings there should be a cycle. If we hit the cycle once we can traverse it many times, so long strings can be pumped. Pumping lemma states that there exits some string s longer than a certain pumping length p and this string could be wr...

DFA to Regular Expression (Example of DFA with 3 states)

DFA to Regular Expression

Regular Expression to NFA

Regular expressions

NFA to DFA

FSM for strings over {0,1} where each 1 is preceded by 0 and the number of 1's is even

FSM for strings over {0,1} for which each 1 is preceded by 0