Context-free grammars versus context-sensitive grammars?

Question

Can someone explain to me why grammars [context-free grammar and context-sensitive grammar] of this kind accepts a String?

What I know is

Context-free grammar is a formal grammar in which every production(rewrite) rule is a form of V→w Where V is a single nonterminal symbol and w is a string of terminals and/or non-terminals. w can be empty

Context-sensitive grammar is a formal grammar in which left-hand sides and right hand sides of any production (rewrite) rules may be surrounded by a context of terminal and nonterminal symbols.

But how can i explain why these grammar accepts a String?

Solution 1

An important detail here is that grammars do not accept strings; they generate strings. Grammars are descriptions of languages that provide a means for generating all possible strings contained in the language. In order to tell if a particular string is contained in the language, you would use a recognizer, some sort of automaton that processes a given string and says "yes" or "no."

A context-free grammar (CFG) is a grammar where (as you noted) each production has the form A → w, where A is a nonterminal and w is a string of terminals and nonterminals. Informally, a CFG is a grammar where any nonterminal can be expanded out to any of its productions at any point. The language of a grammar is the set of strings of terminals that can be derived from the start symbol.

A context-sensitive grammar (CSG) is a grammar where each production has the form wAx → wyx, where w and x are strings of terminals and nonterminals and y is also a string of terminals. In other words, the productions give rules saying "if you see A in a given context, you may replace A by the string y." It's an unfortunate that these grammars are called "context-sensitive grammars" because it means that "context-free" and "context-sensitive" are not opposites, and it means that there are certain classes of grammars that arguably take a lot of contextual information into account but aren't formally considered to be context-sensitive.

To determine whether a string is contained in a CFG or a CSG, there are many approaches. First, you could build a recognizer for the given grammar. For CFGs, the pushdown automaton (PDA) is a type of automaton that accepts precisely the context-free languages, and there is a simple construction for turning any CFG into a PDA. For the context-sensitive grammars, the automaton you would use is called a linear bounded automaton (LBA).

However, these above approaches, if treated naively, are not very efficient. To determine whether a string is contained in the language of a CFG, there are far more efficient algorithms. For example, many grammars can have LL(k) or LR(k) parsers built for them, which allows you to (in linear time) decide whether a string is contained in the grammar. All grammars can be parsed using the Earley parser, which in O(n³) can determine whether a string of length n is contained in the grammar (interestingly, it can parse any unambiguous CFG in O(n²), and with lookaheads can parse any LR(k) grammar in O(n) time!). If you were purely interested in the question "is string x contained in the language generated by grammar G?", then one of these approaches would be excellent. If you wanted to know how the string x was generated (by finding a parse tree), you can adapt these approaches to also provide this information. However, parsing CSGs is, in general, PSPACE-complete, so there are no known parsing algorithms for them that run in worst-case polynomial time. There are some algorithms that in practice tend to run quickly, though. The authors of Parsing Techniques: A Practical Guide (see below) have put together a fantastic page containing all sorts of parsing algorithms, including one that parses context-sensitive languages.

If you're interested in learning more about parsing, consider checking out the excellent book "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which discusses all sorts of parsing algorithms for determining whether a string is contained in a grammar and, if so, how it is generated by the parsing algorithm.

Solution 2

As was said before, a Grammar doesn't accept a string, but it is simply a way in order to generate specific words of a Language that you analyze. In fact, the grammar as the generative rule in the Formal Language Theory instead the finite state automaton do what you're saying, the recognition of specific strings. In particular, you need recursive enumerable automaton in order to recognize Type 1 Languages( the Context Sensitive Languages in the Chomsky's Hierarchy ). A grammar for a specific language only grants to you to specify the property of all the strings which gather to the set of strings of the CS language. I hope that my explanation was clear.

Comments

[user1004413]

is the example in Wiki Grammar, is that example something that i should write to show that grammar accepts a string? But i was wondering how can i relate it to context-free and context-sensitive

[user541686]

Is there any efficient algorithm for parsing strings described by context-sensitive grammars?

[templatetypedef]

@Mehrdad- If I remember correctly, context-sensitive parsing is PSPACE-complete. This means that for some CSGs, unless P = PSPACE, there is no efficient algorithm for parsing strings from that grammar. However, there are a bunch of types of CSGs that have efficient parsing algorithms, though unfortunately I don't know any of them. Searching for "context-sensitive parsing" might be a good way to find them.

[user4205580]

'It's an unfortunate that these grammars are called "context-sensitive grammars" because it means that "context-free" and "context-sensitive" are not opposites' - I don't quite understand it. What do you mean, exactly? What implies they are not opposites? The definitions of CFG and CSG, or their names?

[templatetypedef]

@user4205580 The names "context-free" and "context-sensitive" seem to imply that every grammar is either of one type or the other - either it has no context, or it's sensitive to context. The problem is that this just isn't the case - not all grammars fall into these two categories, nor do all languages. Does that make sense?