Category: Subjects

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.

Grammar in Automata | Types of Grammar

Theory of Automata & Computation

Grammar in Automata-

 

Formal Definition-

 

A Grammar is a 4-tuple such that-

G = (V , T , P , S)

where-

  • V = Finite non-empty set of non-terminal symbols
  • T = Finite set of terminal symbols
  • P = Finite non-empty set of production rules
  • S = Start symbol

 

Grammar Constituents-

 

A Grammar is mainly composed of two basic elements-

 

 

1. Terminal symbols

2. Non-terminal symbols

 

1. Terminal Symbols-

 

  • Terminal symbols are those which are the constituents of the sentence generated using a grammar.
  • Terminal symbols are denoted by using small case letters such as a, b, c etc.

 

2. Non-Terminal Symbols-

 

  • Non-Terminal symbols are those which take part in the generation of the sentence but are not part of it.
  • Non-Terminal symbols are also called as auxiliary symbols or variables.
  • Non-Terminal symbols are denoted by using capital letters such as A, B, C etc.

 

Examples of Grammar-

 

Example-01:

 

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

  • V = { S }                                                  // Set of Non-Terminal symbols
  • T = { a , b }                                              // Set of Terminal symbols
  • P = { S → aSbS , S → bSaS , S → ∈ }   // Set of production rules
  • S = { S }                                                   // Start symbol

 

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

 

Example-02:

 

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

  • V = { S , A , B }                                                  // Set of Non-Terminal symbols
  • T = { a , b }                                                        // Set of Terminal symbols
  • P = { S → ABa , A → BB , B → ab , AA → b }  // Set of production rules
  • S = { S }                                                            // Start symbol

 

Types of Grammars-

 

Grammars are classified on different basis as-

 

 

We will discuss all these types of grammar one by one in detail.

 

Equivalent Grammars-

 

Two grammars are said to be equivalent if they generate the same languages.

 

Also Read- Language of Grammar

 

Example-

 

Consider the following two grammars-

 

Grammar G1-

S → aSb / ∈

 

Grammar G2-

S → aAb / ∈

A → aAb / ∈

 

Both these grammars generate the same language given as-

L = { anbn , n>=0 }

 

Thus, L(G1) = L(G2)

Since both the grammars generate the same language, therefore they are equivalent.

 

∴ G1 ≡ G2

 

To gain better understanding about Grammars in Automata,

Watch this Video Lecture

 

Next Article- Ambiguous Grammar

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Time Complexity of Binary Search Tree

Data Structures

Binary Search Tree-

 

Before you go through this article, make sure that you have gone through the previous article on BST Operations.

 

Commonly performed operations on binary search tree are-

 

 

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

In this article, we will discuss time complexity of BST Operations.

 

Time Complexity-

 

  • Time complexity of all BST Operations = O(h).
  • Here, h = Height of binary search tree

 

Now, let us discuss the worst case and best case.

 

Worst Case-

 

In worst case,

  • The binary search tree is a skewed binary search tree.
  • Height of the binary search tree becomes n.
  • So, Time complexity of BST Operations = O(n).

 

In this case, binary search tree is as good as unordered list with no benefits.

 

 

Best Case-

 

In best case,

  • The binary search tree is a balanced binary search tree.
  • Height of the binary search tree becomes log(n).
  • So, Time complexity of BST Operations = O(logn).

 

 

To gain better understanding about Time Complexity of BST Operations,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Introduction to AVL Trees

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

AVL Tree | AVL Tree Example | AVL Tree Rotation

Data Structures

AVL Tree-

 

  • AVL trees are special kind of binary search trees.
  • In AVL trees, height of left subtree and right subtree of every node differs by at most one.
  • AVL trees are also called as self-balancing binary search trees.

 

Also Read- Binary Search Trees

 

Example-

 

Following tree is an example of AVL tree-

 

 

This tree is an AVL tree because-

  • It is a binary search tree.
  • The difference between height of left subtree and right subtree of every node is at most one.

 

Following tree is not an example of AVL Tree-

 

 

This tree is not an AVL tree because-

  • The difference between height of left subtree and right subtree of root node = 4 – 2 = 2.
  • This difference is greater than one.

 

Balance Factor-

 

In AVL tree,

  • Balance factor is defined for every node.
  • Balance factor of a node = Height of its left subtree – Height of its right subtree

 

In AVL tree,

Balance factor of every node is either 0 or 1 or -1.

 

AVL Tree Operations-

 

Like BST Operations, commonly performed operations on AVL tree are-

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

Also Read- Insertion in AVL Tree

 

After performing any operation on AVL tree, the balance factor of each node is checked.

There are following two cases possible-

 

Case-01:

 

  • After the operation, the balance factor of each node is either 0 or 1 or -1.
  • In this case, the AVL tree is considered to be balanced.
  • The operation is concluded.

 

Case-02:

 

  • After the operation, the balance factor of at least one node is not 0 or 1 or -1.
  • In this case, the AVL tree is considered to be imbalanced.
  • Rotations are then performed to balance the tree.

 

AVL Tree Rotations-

 

Rotation is the process of moving the nodes to make tree balanced.

 

Kinds of Rotations-

 

There are 4 kinds of rotations possible in AVL Trees-

 

 

  1. Left Rotation (LL Rotation)
  2. Right Rotation (RR Rotation)
  3. Left-Right Rotation (LR Rotation)
  4. Right-Left Rotation (RL Rotation)

 

Cases Of Imbalance And Their Balancing Using Rotation Operations-

 

Case-01:

 

 

Case-02:

 

 

Case-03:

 

 

Case-04:

 

 

To gain better understanding about AVL Trees and Rotations,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- AVL Tree Properties

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Relational Algebra | Relational Algebra in DBMS

Database Management System

Relational Algebra-

 

Relational Algebra is a procedural query language which takes a relation as an input and generates a relation as an output.

 

Relational Algebra Operators-

 

The operators in relational algebra may be classified as-

 

 

We will discuss all these operators one by one in detail.

 

Characteristics-

 

Following are the important characteristics of relational operators-

 

  • Relational Operators always work on one or more relational tables.
  • Relational Operators always produce another relational table.
  • The table produced by a relational operator has all the properties of a relational model.

 

Next Article- Selection Operator in Relational Algebra

 

Get more notes and other study material of Database Management System (DBMS).

Watch video lectures by visiting our YouTube channel LearnVidFun.