2.1 CONTEXT-FREE GRAMMARS (Samhengisfrjáls mál)

Question 1

How to describe a context free grammar?

Answer 1

A grammar consists of a collection of substitution rules, also called produc- tions.

Each rule appears as a line in the grammar, comprising a symbol and a string separated by an arrow.

The symbol is called a variable. T

he string consists of variables and other symbols called terminals.

The variable symbols often are represented by capital letters.

The terminals are analogous to the in- put alphabet and often are represented by lowercase letters, numbers, or special symbols.

One variable is designated as the start variable.

Question 2

You use a grammar to describe a language by generating each string of that language in the following manner.

Answer 2

1. Write down the start variable. It is the variable on the left-hand side of the top rule, unless specified otherwise.
2. Find a variable that is written down and a rule that starts with that variable. Replace the written down variable with the right-hand side of that rule.
3. Repeat step 2 until no variables remain.

Question 3

The sequence of substitutions to obtain a string is called a ?

Answer 3

derivation.

Question 4

Any language that can be generated by some context-free grammar is called ?

Answer 4

a context-free language (CFL).

Question 5

A context-free grammar is a 4-tuple (V, Σ, R, S), where

Answer 5

1. V is a finite set called the variables,
2. Σ is a finite set, disjoint from V , called the terminals,
3. R is a finite set of rules, with each rule being a variable and a
   string of variables and terminals, and 4. S ∈ V is the start variable

Question 6

How to construct a complicated CFG?

Answer 6

First, many CFLs are the union of simpler CFLs. If you must construct a CFG for a CFL that you can break into simpler pieces, do so and then construct individual grammars for each piece. These individual grammars can be easily merged into a grammar for the original language by combining their rules and then adding the new rule S → S1 | S2 |

Question 7

How do convert any DFA into an equivalent CFG?

Answer 7

Make a variable Ri for each state qi of the DFA. Add the rule Ri → aRj to the CFG if δ(qi,a) = qj is a transition in the DFA. Add the rule Ri → ε if qi is an accept state of the DFA. Make R0 the start variable of the grammar, where q0 is the start state of the machine. Verify on your own that the resulting CFG generates the same language that the DFA recognizes.

Question 8

AMBIGUITY

Answer 8

If a grammar generates the same string in several different ways, we say that the string is derived ambiguously in that grammar. If a grammar generates some string ambiguously, we say that the grammar is ambiguous.

Question 9

A string w is derived ambiguously in context-free grammar G if it has two or more different leftmost derivations. Grammar G is ambiguous if it generates some string ambiguously.

Question 10

Some context-free languages, however, can be generated only by ambiguous grammars. Such languages are called ?

Answer 10

inherently ambiguous.

Question 11

Chomsky normal form

Answer 11

A context-free grammar is in Chomsky normal form if every rule is of the form
A → BC A→a
where a is any terminal and A, B, and C are any variables—except that B and C may not be the start variable. In addition, we permit the rule S → ε, where S is the start variable.

Question 12

Any context-free language is generated by a context-free grammar in Chomsky
normal form.