Regular vs Context Free Grammars

Question

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around.

I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for programming languages. I also understood that context-free grammars allow ambiguity, but allow for some things necessary for programming languages (like palindromes).

What I'm having trouble with is understanding how I can derive all of the above by knowing that regular grammar nonterminals can map to a terminal or a nonterminal followed by a terminal or that a context-free nonterminal maps to any combination of terminals and nonterminals.

Can someone help me put all of this together?

Mallory

Answer 1

Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar.

So for a palindrome for instance, is of the form,

S->ABA
A->something
B->something

You can clearly see that palindromes cannot be expressed in regular grammar since it needs to be either right or left linear and as such cannot have a non-terminal on both side.

Since regular grammars are non-ambiguous, there is only one production rule for a given non-terminal, whereas there can be more than one in the case of a context-free grammar.

Evacuee

First: Regular grammars can be ambiguous (example from Kai Kuchenbecker: S -> aA | aB, B -> a, A -> a). The only thing is that there is only one way the nodes in the syntax tree can be positioned (for instance the associativity ambiguity does not exist when a regular grammar is used). Second: There can be more than one right hand side to a non-terminal (A -> a, A -> aA; and wikipedia even includes epsilon as an third alternative: en.wikipedia.org/wiki/Regular_grammar) – Materially

ambiguity comes when a sentence can be derived from your grammar in more than one derivation path. simply having more than one production rule for a non-terminal does not make the grammar ambiguous – Evacuee

This example is actually wrong. If we imagine the full rules to be A-> a | c and B->b then this grammar allows non-palindromes. For example, I could produce: S->ABA->aBA->abA->abc. The problem is that we don't want to produce two variables in the first rule, but rather two terminals. A possibility for a grammar that allows palindromes is: S -> aSa | bSb | a | b – Fortuity

There are palindromes that can be expressed in a regular grammar: the palindromes that consist of a single character. For example, S -> aSa | e and a(aa)*a both describe a regular language. This shows that a CFG can describe a regular language, even if it violates the left or right linearity. Admittedly, this is a not-so-obvious palindrome.. – Camelliacamelopard

Come to think of it, this answer is actually wrong. It says "context-free" grammar is basically any combination of terminals and non-terminals." However, tu^nvw^mxy^kz is a combination of terminals and nonterminals, but not context-free. – Skipper

Answer 2

I think what you want to think about are the various pumping lemmata. A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine.)

So, if we think about the pumping lemma for regular languages, what it says, essentially, is that any regular language can be broken down into three pieces, x, y, and z, where all instances of the language are in xy*z (where * is Kleene repetition, ie, 0 or more copies of y.) You basically have one "nonterminal" that can be expanded.

Now, what about context-free languages? There's an analogous pumping lemma for context-free languages that breaks the strings in the language into five parts, uvxyz, and where all instances of the language are in uvⁱxyⁱz, for i ≥ 0. Now, you have two "nonterminals" that can be replicated, or pumped, as long as you have the same number.

Skipper

A context sensitive language does not require a full Turing machine. A linear bounded automaton is sufficient. This is a Turing machine whose tape is finite, the size is bounded by some linear function on the input string. – Spatial

Answer 3

The difference between regular and context free grammar: (N, Σ, P, S) : terminals, nonterminals, productions, starting state Terminal symbols

● elementary symbols of the language defined by a formal grammar

● abc

Nonterminal symbols (or syntactic variables)

● replaced by groups of terminal symbols according to the production rules

● ABC

regular grammar: right or left regular grammar right regular grammar, all rules obey the forms

1. B → a where B is a nonterminal in N and a is a terminal in Σ
2. B → aC where B and C are in N and a is in Σ
3. B → ε where B is in N and ε denotes the empty string, i.e. the string of length 0

left regular grammar, all rules obey the forms

1. A → a where A is a nonterminal in N and a is a terminal in Σ
2. A → Ba where A and B are in N and a is in Σ
3. A → ε where A is in N and ε is the empty string

context free grammar (CFG)

○ formal grammar in which every production rule is of the form V → w

○ V is a single nonterminal symbol

○ w is a string of terminals and/or nonterminals (w can be empty)

Toleration

Answer 4

Regular grammar:- grammar containing production as follows is RG:

V->TV or VT
V->T

where V=variable and T=terminal

RG may be Left Linear Grammar or Right Liner Grammar, but not Middle linear Grammar.

As we know all RG are Linear Grammar but only Left Linear or Right Linear Grammar are RG.

A regular grammar can be ambiguous.

S->aA|aB
A->a
B->a

Ambiguous Grammar:- for a string x their exist more than one LMD or More than RMD or More than one Parse tree or One LMD and One RMD but both Produce different Parse tree.

                S                   S

              /   \               /   \
             a     A             a     B
                    \                   \
                     a                   a

this Grammar is ambiguous Grammar because two parse tree.

CFG:- A grammar said to be CFG if its Production is in form:

   V->@   where @ belongs to (V+T)*

DCFL:- as we know all DCFL are LL(1) Grammar and all LL(1) is LR(1) so it is Never be ambiguous. so DCFG is Never be ambiguous.

We also know all RL are DCFL so RL never be ambiguous. Note that RG may be ambiguous but RL not.

CFL: CFl May or may not ambiguous.

Note: RL never be Inherently ambiguous.

Foulness

Answer 5

Regular Expressions

• Basis of lexical analysis
• Represent regular languages

Context Free Grammars

• Basis of parsing
• Represent language constructs

Tetartohedral

Nope, that is short description, please read again and check the image. – Tetartohedral

Answer 6

A grammar is context-free if all production rules have the form: A (that is, the left side of a rule can only be a single variable; the right side is unrestricted and can be any sequence of terminals and variables). We can define a grammar as a 4-tuple where V is a finite set (variables), _ is a finite set (terminals), S is the start variable, and R is a finite set of rules, each of which is a mapping V
regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. hence we can say that regular grammar is a subset of context-free grammar. After these properties we can say that Context Free Languages set also contains Regular Languages set

Technician

Answer 7

Basically regular grammar is a subset of context free grammar,but we can not say Every Context free grammar is a regular grammar. Mainly context free grammar is ambiguous and regular grammar may be ambiguous.

Sarcasm

Answer 8

a regular grammer is never ambiguous because it is either left linear or right linear so we cant make two decision tree for regular grammer so it is always unambiguous.but othert than regular grammar all are may or may not be regular

Mccrae

@Mccrae A regular grammar can be ambiguous. Recall that a grammar is ambiguous if there exist two different syntax trees and that a syntax tree is labeled. Hence isomorphic trees are different trees. I.e. a simple grammar like S -> aA | aB, B -> a, A -> a is ambiguous since there exist two syntax trees for the word 'aa' that are isomorphic but different. – Schober