Formal languages | Grammar frameworks

Context-sensitive grammar

A context-sensitive grammar (CSG) is a formal grammar in which the left-hand sides and right-hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context-sensitive grammars are more general than context-free grammars, in the sense that there are languages that can be described by CSG but not by context-free grammars. Context-sensitive grammars are less general (in the same sense) than unrestricted grammars. Thus, CSG are positioned between context-free and unrestricted grammars in the Chomsky hierarchy. A formal language that can be described by a context-sensitive grammar, or, equivalently, by a noncontracting grammar or a linear bounded automaton, is called a context-sensitive language. Some textbooks actually define CSGs as non-contracting, although this is not how Noam Chomsky defined them in 1959. This choice of definition makes no difference in terms of the languages generated (i.e. the two definitions are weakly equivalent), but it does make a difference in terms of what grammars are structurally considered context-sensitive; the latter issue was analyzed by Chomsky in 1963. Chomsky introduced context-sensitive grammars as a way to describe the syntax of natural language where it is often the case that a word may or may not be appropriate in a certain place depending on the context. Walter Savitch has criticized the terminology "context-sensitive" as misleading and proposed "non-erasing" as better explaining the distinction between a CSG and an unrestricted grammar. Although it is well known that certain features of languages (e.g. cross-serial dependency) are not context-free, it is an open question how much of CSG's expressive power is needed to capture the context sensitivity found in natural languages. Subsequent research in this area has focused on the more computationally tractable mildly context-sensitive languages. The syntaxes of some visual programming languages can be described by context-sensitive graph grammars. (Wikipedia).

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

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

Javascript Context Tutorial - What makes Javascript Weird...and Awesome Pt5

View whole series here: https://www.youtube.com/playlist?list=PLoYCgNOIyGABI011EYc-avPOsk1YsMUe_ Call, Apply & Bind are avoided by many JS developers, but it doesn't have to be that way. Context is a simple concept that creates complicated realities for developers. In this javascript tu

From playlist Javascript Tutorial For Beginners

Video thumbnail

ADVERBS of TIME, FREQUENCY, LOCATION, and MANNER - ENGLISH GRAMMAR

We talk about adverbs of location, adverbs of time, adverbs of manner, and adverbs of frequency. Adverbs modify verbs or add background information for an entire sentence. #EnglishGrammar #Grammar #English If you want to support the channel, hit the "JOIN" button above and pick a channel

From playlist English Grammar

Video thumbnail

Javascript Scope Tutorial - What Makes Javascript Weird...and Awesome Pt 4

Scope and Context are in every language, but because Javascript is always firing callbacks and running asynchronous tasks, it's easy to lose sight of what scope & context you're in. Scope and context are not the same thing. Scope is variable access - what variables the current piece of c

From playlist Javascript Tutorial For Beginners

Video thumbnail

Context Free Languages

Theory of Computation 5. Context Free Languages ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

RubyConf 2015 - Botany with Bytes by Lito Nicolai

Botany with Bytes by Lito Nicolai Plants are tiny computers. As they grow, the sprouts are computing from first principles how to be a plant. We’ll see how they do it! This talk uses Ruby and the ‘graphics’ gem to build models of all kinds of plants, from algae blooms to juniper branches

From playlist RubyConf 2015

Video thumbnail

Black Hat USA 2010: Exploiting the Forest with Trees 2/5

Speakers: Meredith L. Patterson, Len Sassaman One of the most difficult aspects of securing a protocol implementation is simply bounding the scope of the attack surface: how do you tell where attacks are likely to crop up? Historically, variations between implementations have led to some

From playlist Black Hat USA 2010

Video thumbnail

More lemmas, CYK

Theory of Computation 9. More lemmas, CYK ADUni

From playlist [Shai Simonson]Theory of Computation

Video thumbnail

Program Language Translation Using a Grammar-Driven Tree-to-Tree Model | TDLS

Toronto Deep Learning Series, 30 July 2018 For slides and more information, visit https://tdls.a-i.science/events/2018-07-30/ Paper Review: https://arxiv.org/abs/1807.01784 Speaker: Alex Hesammohseni Organizer: https://www.linkedin.com/in/amirfz/ Host: Microsoft Canada Paper abstract:

From playlist Natural Language Processing

Video thumbnail

Monadic Parsers at the Input Boundary

When reading a byte stream over the process I/O boundary, the first thing which everyone should do is to parse the byte stream with a monadic parser. The talk will discuss Processes and input byte streams. Monadic parsers. What they are and why they matter. The design and use of the pure

From playlist Functional Programming

Video thumbnail

LA Rubyconf 2015- Botany with Bytes by Lito Nicolai

Botany with Bytes Plants are tiny computers. As they grow, the sprouts are computing from first principles how to be a plant. We’ll see how they do it! This talk uses Ruby and the ‘graphics’ gem to build models of all kinds of plants, from algae blooms to juniper branches. We’ll touch on

From playlist LA Rubyconf 2015

Video thumbnail

Grammar: Who's or Whose?

In this video, you’ll learn more about when to use "whose" and "who's" correctly in American English. Visit https://www.gcflearnfree.org/grammar/whos-or-whose/1/ for our text-based lesson. We hope you enjoy!

From playlist Grammar

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

Psych9B. Psychology Fundamentals. Lecture 12

UCI Psych 9B: Psych Fundamentals (Fall 2015) Lec 12. Psych Fundamentals View the complete course: http://ocw.uci.edu/courses/psych_9bpsy_beh_11b_psychology_fundamentals.html Instructor: Mark Steyvers, Ph.D. License: Creative Commons CC-BY-SA Terms of Use: http://ocw.uci.edu/info. More cou

From playlist Psych 9B: Psych Fundamentals

Related pages

Context-free language | Decision problem | Intersection (set theory) | Context-free grammar | Tree-adjoining grammar | John Myhill | Definite clause grammar | Formal grammar | Complement (set theory) | Kuroda normal form | Formal language | Context-sensitive language | Combinatory categorial grammar | Emptiness problem | Production (computer science) | Union (set theory) | Concatenation | PSPACE-complete | Growing context-sensitive grammar | Chomsky hierarchy | Linear bounded automaton | Noncontracting grammar | Empty string | Unrestricted grammar | Immerman–Szelepcsényi theorem | Recursively enumerable language | Range concatenation grammar | Generalized context-free grammar