CODEWITHSUNDEEP
grammarcontext-free-grammarautomatacontext-free-language
Ejaz Ahamed
Ejaz Ahamed

Reputation: 31

Construct a grammar for a language

I have a question regarding this question:

L= empty where the alphabet is {a,b}

how to create a grammar for this ? how can be the production rule ? thanks in advance

Upvotes: 0

Views: 670

Answers (1)

Patrick87
Patrick87

Reputation: 28292

A grammar G is an ordered 4-tuple {S, N, E, e, P} where:

  1. N is a set of non-terminal symbols
  2. E is a set of terminal symbols
  3. N and E are disjoint
  4. E is a superset of the alphabet of L(G)
  5. e is the empty string
  6. P is a set of ordered pairs of elements of (N U E U e); that is, P is a subset of (N U E U e) X (N U E U e)*.
  7. S, the start symbol, is in N

A derivation in G is a sequence of elements of (N U E U e)* such that:

  1. The first element is S
  2. Adjacent elements w[i] and w[i+1] can be written as w[i] = uxv and w[i+1] = uyv such that (x, y) is in P

If there is a derivation in G whose last element is a string w[n] over (E U e)*, we say G generates w[n]; that is, w[n] is in L(G).

Now, we want to define a grammar G such that L(G) is the empty set. We fix the alphabet E = {a, b}. We must still define:

  1. N, the set of nonterminals
  2. S, the start symbol
  3. P, the productions

We might as well take S as our start symbol. So N contains at least S; N is a superset of {S}. We will only add more nonterminals if we determine we need them. Let us turn our attention to the condition that L(G) is empty.

If L(G) is empty, that means there is no derivation in G that leads to a string of only terminal symbols. We can accomplish this easily be ensuring all our productions produce at least one nonterminal with any terminal. Or produce no terminals at all. So the following grammars would all work:

S := S

or

S := aSb

or

S := aXb | XXSSX
X := aabbXbbaaS

etc. All of these grammars have L(G) empty since none of them can derive a string of nonterminals.

Upvotes: 1

Related Questions