Tag: Infinite Language

Language Ambiguity | Ambiguous Language

Theory of Automata & Computation

Language Of Grammar-

 

Before you go through this article, make sure that you have gone through the previous article on Language of Grammar.

 

We have discussed-

  • Language of grammar is the set of all strings that can be generated from that grammar.
  • Finite language consists of finite number of strings.
  • Infinite language consists of infinite number of strings.

 

In this article, we will discuss about Language Ambiguity.

 

Language Ambiguity-

 

If every grammar that generates language L is ambiguous,

then language L is called as Inherently ambiguous language.

OR

A language is inherently ambiguous if all the grammars which generate that language are ambiguous.

 

Also Read- Ambiguous Grammar

 

NOTE-

 

  • The term “inherently ambiguous language” is used instead of “ambiguous language”.
  • This is because all the grammars which generate that language are ambiguous.

 

Important Points-

 

  • If a grammar is ambiguous, it does not imply that its language will be ambiguous too.
  • If a grammar is ambiguous, its language may be unambiguous.
  • If a grammar is ambiguous, its language will be unambiguous when there exists at least one unambiguous grammar which generates that language.

 

Example Of Not An Inherently Ambiguous Language-

 

Consider the following language-

L = an , n>=0

 

  • This language consists of strings having any number of a’s.
  • Few grammars which generate this language are-

 

Grammar-01:

 

S → aS / ∈

(Unambiguous Grammar)

 

Grammar-02:

 

S → aS / a / ∈

(Ambiguous Grammar)

 

Grammar-03:

 

S → aS / Sa / ∈

(Ambiguous Grammar)

 

Grammar-04:

 

S → aS / a / Sa / ∈

(Ambiguous Grammar)

 

  • All the above grammars generate the same language L = an , n>=0.
  • Grammar-01 is unambiguous.
  • Since there exists at least one unambiguous grammar which generates language L.
  • Therefore, L is not an inherently ambiguous language.

 

Example Of An Inherently Ambiguous Language-

 

Consider the following language-

L = { anbncm } ∪ { anbmcm }

 

There exists only one grammar which generates this language L.

The grammar is-

 

S → S1 / S2

S1 → S1C / A

A → aAb / ∈

S2 → aS2 / B

B → bBc / ∈

 

This grammar is ambiguous in nature.

This is because following two parse trees exist for string w = abc-

 

Also Read- Checking Grammar Ambiguity

 

 

  • There exists no language that generates this language L and is unambiguous.
  • Therefore, L is an inherently ambiguous language.

 

Next Article- Context Free Grammar

 

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Language Of Grammar | Automata

Theory of Automata & Computation

Language Of Grammar-

 

Language of Grammar is the set of all strings that can be generated from that grammar.

 

  • If the language consists of finite number of strings, then it is called as a Finite language.
  • If the language consists of infinite number of strings, then it is called as an Infinite language.

 

Also Read- Grammar in Automata

 

Example-01:

 

Consider a grammar G = (V , T , P , S) where-

  • V = { S }
  • T = { a , b }
  • P = { S → aSbS , S → bSaS , S → ∈ }
  • S = { S }

 

This grammar generates the strings having equal number of a’s and b’s.

 

So, Language of this grammar is-

 

L(G) = { ∈ , ab , ba , aabb , bbaa , abab , baba , …… }

 

  • This language consists of infinite number of strings.
  • Therefore, language of the grammar is infinite.

 

Example-02:

 

Consider a grammar G = (V , T , P , S) where-

  • V = { S , A , B , C }
  • T = { a , b , c }
  • P = { S → ABC , A → a , B → b , C → c }
  • S = { S }

 

This grammar generates only one string “abc”.

 

So, Language of this grammar is-

 

L(G) = { abc }

 

  • This language consists of finite number of strings.
  • Therefore, language of the grammar is finite.

 

Also Read- Deciding Language Is Finite Or Infinite

 

Important Concept-

 

  • For any given grammar, the language generated by it is always unique.
  • For any given language, we may have more than one grammar generating that language.

 

 

Example-

 

Consider the following two grammars-

 

Grammar G1-

 

S → AB

A → a

B → b

The language generated by this grammar is-

L(G1) = { ab }

 

Grammar G2-

 

S → AB

A → ∈

B → ab

The language generated by this grammar is-

L(G2) = { ab }

 

Here,

  • Both the grammars generate a unique language.
  • But given a language L(G) = { ab }, we have two different grammars generating that language.

This justifies the above concept.

 

Next Article- Language Ambiguity

 

Get more notes and other study material of Theory of Automata and Computation.

Watch video lectures by visiting our YouTube channel LearnVidFun.