- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Firstly, let us learn about the infinite language and then understand how to construct the finite and infinite language in the theory of computation (TOC).

**Infinite language**

There is no bound on the length of any strings in an infinite language.

There is no bound on any number of derivation steps used to derive the strings also.

For example, if the grammar has n productions, then any derivation consisting of n + 1 steps uses some production twice.

If the language is said to be infinite, then some production or sequence of productions must be used repeatedly to construct the derivations

**Example**

The infinite language {anb | n > 0} is described by the grammar,

S → b | aS.

To derive the string anb, use the production S → aS repeatedly n times and then stop the derivation by using the production S → b.

The production S → aS allows us to say

“If S derives p, then it derives ap also.”

**Construct grammar**

Let us understand how to construct grammar for an infinite language.

There is no universal method for finding a grammar for an infinite language, so we need to think. However, the method of combining grammars can be useful.

**Example**

Find a grammar for the following simple language −

{∧, a, aa, . . . , an, . . . } = {an: n ∈ N}

**Solution**

The set of terminals − T = {a},

The only non-terminal start symbol S,

The set of production rules −

S → ∧, S → aS

**Construct grammar for finite language**

Now, we have the opposite problem of finding a grammar for a given language.

Sometimes it is difficult or even impossible to write down a grammar for a given language. Moreover, not surprisingly, a language might have more than one grammar.

If the number of strings in a language is finite, then a grammar can consist of all productions of the form S → w for each string w in the language.

**Example**

The finite language {a, ba} can be described by the grammar as given below −

S → a | ba

- Related Questions & Answers
- Efficient Construction of Finite Automata
- Explain the construction and working of a Microwave Varactor diode.
- Explain the construction and working of a Microwave Schottky Barrier diode.
- Explain the relationship between Finite Automata and Regular Expression.
- Explain the history of C language?
- Explain the Format of C language
- Explain the equivalence between two Finite State Machines.
- Explain the characteristics and operations of arrays in C language
- Explain the concepts of Pointers and arrays in C language
- Explain the Star Height of Regular Expression and Regular Language
- Explain Deterministic Finite Automata in TOC.
- Explain the method for constructing Minimum Finite State Automata.
- Explain the concept of logical and assignment operator in C language
- Explain Non-Deterministic Finite Automata in TOC.
- Explain the concept of pointers in C language

Advertisements