Formal languages

Deterministic context-free grammar

In formal grammar theory, the deterministic context-free grammars (DCFGs) are a proper subset of the context-free grammars. They are the subset of context-free grammars that can be derived from deterministic pushdown automata, and they generate the deterministic context-free languages. DCFGs are always unambiguous, and are an important subclass of unambiguous CFGs; there are non-deterministic unambiguous CFGs, however. DCFGs are of great practical interest, as they can be parsed in linear time and in fact a parser can be automatically generated from the grammar by a parser generator. They are thus widely used throughout computer science. Various restricted forms of DCFGs can be parsed by simpler, less resource-intensive parsers, and thus are often used. These grammar classes are referred to by the type of parser that parses them, and important examples are LALR, SLR, and LL. (Wikipedia).

Video thumbnail

How a Computer know a Sentence is Grammatical: Context Free Grammars [Lecture]

This is a single lecture from a course. If you you like the material and want more context (e.g., the lectures that came before), check out the whole course: https://boydgraber.org/teaching/CMSC_723/ (Including homeworks and reading.) Music: https://soundcloud.com/alvin-grissom-ii/review

From playlist Computational Linguistics I

Video thumbnail

7.1: Intro to Session 7: Context-Free Grammar - Programming with Text

This video introduces Session 7: Context-Free Grammar from the ITP course "Programming from A to Z". A Context-Free Grammar is a set of recursive "replacement" rules to generate text. In this session, I discuss two JavaScript libraries: Tracery and RiTa.js for working with context-free gr

From playlist Programming with Text - All Videos

Video thumbnail

Context Free Languages

Theory of Computation 5. Context Free Languages ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

Building context-free grammars: Theory of Computation (Mar 12 2021)

Context free grammars! This is a recording of a live class for Math 3342, Theory of Computation, an undergraduate course for math & computer science majors at Fairfield University, Spring 2021. Class website: http://cstaecker.fairfield.edu/~cstaecker/courses/2021s3342/

From playlist Math 3342 (Theory of Computation) Spring 2021

Video thumbnail

CFGs and NPDMs

Theory of Computation 8. CFGs and NPDMs ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

Undecidability and CFLs

Theory of Computation 10. Undecidability and CFLs ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

More lemmas, CYK

Theory of Computation 9. More lemmas, CYK ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

MIT 18.404J Theory of Computation, Fall 2020 Instructor: Michael Sipser View the complete course: https://ocw.mit.edu/18-404JF20 YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY Quickly reviewed last lecture. Defined context free grammars (CFGs) a

From playlist MIT 18.404J Theory of Computation, Fall 2020

Video thumbnail

CONCRETE NOUNS and ABSTRACT NOUNS - ENGLISH GRAMMAR

Concrete nouns are nouns that can be heard, tasted, smelled, touched, or seen. Abstract nouns are nouns that can be believed, felt emotionally, understood, learned, or known. LIKE AND SHARE THE VIDEO IF IT HELPED! Support me on Patreon: http://bit.ly/2EUdAl3 Visit our website: http://

From playlist English Grammar

Video thumbnail

Theory of Computation Recitation 5

Theory of Computation Recitation 5 aduni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

14. P and NP, SAT, Poly-Time Reducibility

MIT 18.404J Theory of Computation, Fall 2020 Instructor: Michael Sipser View the complete course: https://ocw.mit.edu/18-404JF20 YouTube Playlist: https://www.youtube.com/playlist?list=PLUl4u3cNGP60_JNv2MmK3wkOt9syvfQWY Quickly reviewed last lecture. Defined NTIME(t(n)) complexity classes

From playlist MIT 18.404J Theory of Computation, Fall 2020

Video thumbnail

Pushdown Machines

Theory of Computation 7. Pushdown Machines ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

Compilation – Why learn about compilers?

As you will see when you watch this series, compilation involves a diverse range of themes in the field of computer science including high and low level programming paradigms, the definition of context free grammars, the application of dynamic data structures such as stacks, linked lists,

From playlist Compilation

Video thumbnail

CFLs and compilers

Theory of Computation 6. CFLs and compilers ADUni

From playlist [Shai Simonson]Theory of Computation

Related pages

Formal grammar | Deterministic pushdown automaton | LR parser | LL parser | Deterministic context-free language