Category: Subjects

Convert to Base 10 | Number System Conversions

Number System

Number System Conversions-

 

Before you go through this article, make sure that you have gone through the previous article on Basics of Number System.

 

In number system,

  • It is very important to have a good knowledge of how to convert numbers from one base to another base.
  • Here, we will learn how to convert any given number from any base to base 10.

 

 

Converting to Base 10-

 

A given number can be converted from any base to base 10 using Expansion Method.

According to expansion method, if abc.de is any given number in base x, then its value in base 10 is given as-

 

(abc.de)x = (ax2 + bx + c + dx-1 + ex-2)10

 

Explanation-

 

To use expansion method for conversion,

  • Assign position number to each digit of the given number.
  • Digits to the left of decimal are numbered starting from 0.
  • Digits to the right of decimal are numbered starting from -1.
  • Write a term for each digit as digit x (base of given number)position number of digit
  • Perform the addition of all terms to obtain the number in base 10.
  • This formula can be expanded for any number of digits.

 

 

PRACTICE PROBLEMS BASED ON CONVERSION TO BASE 10-

 

Convert the following numbers to base 10-

  1. (10010)2
  2. (254)8
  3. (AC)16
  4. (10010.101)2
  5. (254.7014)8
  6. (AC.FBA5)16
  7. (0.1402)8
  8. (0.ABDF)16

 

Solutions-

 

1. (10010)2

 

(10010)2 → ( ? )10

 

Using expansion method, we have-

(10010)2

= ( 1 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 0 x 20 )10

= ( 16 + 0 + 0 + 2 + 0 )10

= ( 18 )10

 

2. (254)8

 

(254)8 → ( ? )10

 

Using expansion method, we have-

(254)8

= ( 2 x 82 + 5 x 81 + 4 x 80 )10

= ( 128 + 40 + 4 )10

= ( 172 )10

 

3. (AC)16

 

(AC)16 → ( ? )10

 

Using expansion method, we have-

(AC)16

= ( A x 161 + C x 160 )10

= ( 10 x 16 + 12 x 1 )10

= ( 160 + 12 )10

= ( 172 )10

 

4. (10010.101)2

 

(10010.101)2 → ( ? )10

 

Using expansion method, we have-

(10010.101)2

= ( 1 x 24 + 0 x 23 + 0 x 22 + 1 x 21 + 0 x 20 + 1 x 2-1 + 0 x 2-2 + 1 x 2-3 )10

= ( 16 + 0 + 0 + 2 + 0 + 0.5 + 0.125 )10

= ( 18.625 )10

 

5. (254.7014)8

 

(254.7014)8 → ( ? )10

 

Using expansion method, we have-

(254.7014)8

= ( 2 x 82 + 5 x 81 + 4 x 80 + 7 x 8-1 + 0 x 8-2 + 1 x 8-3 + 4 x 8-4 )10

= ( 128 + 40 + 4 + 0.875 + 0.0019 + 0.0009 )10

= ( 172.8778 )10

 

6. (AC.FBA5)16

 

(AC.FBA5)16 → ( ? )10

 

Using expansion method, we have-

(AC.FBA5)16

= ( A x 161 + C x 160 + F x 16-1 + B x 16-2 + A x 16-3 + 5 x 16-4 )10

= ( 10 x 16 + 12 x 1 + 15 x 16-1 + 11 x 16-2 + 10 x 16-3 + 5 x 16-4 )10

= ( 160 + 12 + 0.9375 + 0.0429 + 0.0024 + 0.0001 )10

= ( 172.9829 )10

 

7. (0.1402)8

 

(0.1402)8 → ( ? )10

 

Using expansion method, we have-

(0.1402)8

= ( 0 x 80 + 1 x 8-1 + 4 x 8-2 + 0 x 8-3 + 2 x 8-4 )10

= ( 0 + 0.125 + 0.0625 + 0 + 0.0005 )10

= ( 0.188 )10

 

8. (0.ABDF)16

 

(0.ABDF)16 → ( ? )10

 

Using expansion method, we have-

(0.ABDF)16

= ( 0 x 160 + A x 16-1 + B x 16-2 + D x 16-3 + F x 16-4 )10

= ( 0 x 1 + 10 x 16-1 + 11 x 16-2 + 13 x 16-3 + 15 x 16-4 )10

= ( 0 + 0.625 + 0.0429 + 0.0032 + 0.0002 )10

= ( 0.6713 )10

 

To gain better understanding about Conversion to Base 10,

Watch this Video Lecture

 

Next Article- Decimal to Binary Conversion

 

Get more notes and other study material of Number System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Base of Number System | Types of Number System

Number System

Base of Number System-

 

  • Base of a number system is the total number of digits used in that number system.
  • Number system with base ‘b’ has its digits in the range [0 , b-1].
  • It is also called as radix of a number system.

 

Examples-

 

Consider the following examples-

 

Base 10 Number System-

 

Consider base 10 number system popularly called as decimal number system-

  • Total number of digits used in this number system are 10 since it has base 10.
  • These digits are 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9.
  • These digits clearly lie in the range [0 , base-1] = [0 , 9].

 

Base 2 Number System-

 

Consider base 2 number system popularly called as binary number system-

  • Total number of digits used in this number system are 2 since it has base 2.
  • These digits are 0 and 1.
  • These digits clearly lie in the range [0 , base-1] = [0 , 1].

 

Important Note-

 

It is important to note that-

  • All the digits of any number system with base ‘b’ are always less than ‘b’.
  • This is clear from the range [0 , base-1] in which the digits of any number system lie.

 

Types of Number System-

 

Four most commonly used number systems are-

 

 

  1. Decimal Number System
  2. Binary Number System
  3. Octal Number System
  4. Hexadecimal Number System

 

The following table shows the base and digits used in these number systems-

 

Number System Base Digits Used
Decimal Number System 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

(Total 10 digits)
Binary Number System 2 0, 1

(Total 2 digits)
Octal Number System 8 0, 1, 2, 3, 4, 5, 6, 7

(Total 8 digits)
Hexadecimal Number System 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

(Total 16 digits)

 

To gain better understanding about Basics of Number System,

Watch this Video Lecture

 

Next Article- Converting Any Base to Base 10

 

Get more notes and other study material of Number System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

DFA Solved Examples | How to Construct DFA

Theory of Automata & Computation

Construction Of DFA-

 

Before you go through this article, make sure that you have gone through the previous article on Type-01 Problems.

 

Type-02 Problems-

 

In Type-02 problems, we will discuss the construction of DFA for languages consisting of strings starting with a particular substring.

 

Steps To Construct DFA-

 

Following steps are followed to construct a DFA for Type-02 problems-

 

Step-01:

 

  • Determine the minimum number of states required in the DFA.
  • Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE

Calculate the length of substring.

All strings starting with ‘n’ length substring will always require minimum (n+2) states in the DFA.

 

Step-02:

 

  • Decide the strings for which DFA will be constructed.
  • The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

  • Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE

While constructing a DFA,

  • Always prefer to use the existing path.
  • Create a new path only when there exists no path to go with.

 

Step-04:

 

  • Send all the left possible combinations to the dead state.
  • Do not send the left possible combinations over the starting state.

 

PRACTICE PROBLEMS BASED ON CONSTRUCTION OF DFA-

 

Problem-01:

 

Draw a DFA for the language accepting strings starting with ‘ab’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = ab(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “ab”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • ab
  • aba
  • abab

 

Step-03:

 

The required DFA is-

 

Problem-02:

 

Draw a DFA for the language accepting strings starting with ‘a’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = a(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “a”.
  • So, length of substring = 1.

 

Thus, Minimum number of states required in the DFA = 1 + 2 = 3.

It suggests that minimized DFA will have 3 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • a
  • aa

 

Step-03:

 

The required DFA is-

 

Problem-03:

 

Draw a DFA for the language accepting strings starting with ‘101’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = 101(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “101”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 101
  • 1011
  • 10110
  • 101101

 

Step-03:

 

The required DFA is-

 

Problem-04:

 

Draw a DFA that accepts a language L over input alphabets ∑ = {0, 1} such that L is the set of all strings starting with ’00’.

 

Solution-

 

Regular expression for the given language = 00(0 + 1)*

 

Step-01:

 

  • All strings of the language starts with substring “00”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 2 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 00
  • 000
  • 00000

 

Step-03:

 

The required DFA is-

 

Problem-05:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aa’ or ‘bb’.

 

Solution-

 

Regular expression for the given language = (aa + bb)(a + b)*

 

Step-01:

 

Minimum number of states required in the DFA = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aa
  • aaa
  • aaaa
  • bb
  • bbb
  • bbbb

 

Step-03:

 

The required DFA is-

 

Problem-06:

 

Construct a DFA that accepts a language L over input alphabets ∑ = {a, b} such that L is the set of all strings starting with ‘aba’.

 

Solution-

 

Regular expression for the given language = aba(a + b)*

 

Step-01:

 

  • All strings of the language starts with substring “aba”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 2 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • aba
  • abaa
  • abaab
  • abaaba

 

Step-03:

 

The required DFA is-

 

Also Read- Converting DFA to Regular Expression

 

To gain better understanding about Construction of DFA,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Minimization of DFA

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Construction of DFA | DFA Solved Examples

Theory of Automata & Computation

Construction Of DFA-

 

In this article, we will learn the construction of DFA.

 

Type-01 Problems-

 

In Type-01 problems, we will discuss the construction of DFA for languages consisting of strings ending with a particular substring.

 

Steps To Construct DFA-

 

Following steps are followed to construct a DFA for Type-01 problems-

 

Step-01:

 

  • Determine the minimum number of states required in the DFA.
  • Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE

Calculate the length of substring.

All strings ending with ‘n’ length substring will always require minimum (n+1) states in the DFA.

 

Step-02:

 

  • Decide the strings for which DFA will be constructed.
  • The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

  • Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE

While constructing a DFA,

  • Always prefer to use the existing path.
  • Create a new path only when there exists no path to go with.

 

Step-04:

 

  • Send all the left possible combinations to the starting state.
  • Do not send the left possible combinations over the dead state.

 

PRACTICE PROBLEMS BASED ON CONSTRUCTION OF DFA-

 

Problem-01:

 

Draw a DFA for the language accepting strings ending with ’01’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = (0 + 1)*01

 

Step-01:

 

  • All strings of the language ends with substring “01”.
  • So, length of substring = 2.

 

Thus, Minimum number of states required in the DFA = 2 + 1 = 3.

It suggests that minimized DFA will have 3 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 01
  • 001
  • 0101

 

Step-03:

 

The required DFA is-

 

 

Problem-02:

 

Draw a DFA for the language accepting strings ending with ‘abb’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = (a + b)*abb

 

Step-01:

 

  • All strings of the language ends with substring “abb”.
  • So, length of substring = 3.

 

Thus, Minimum number of states required in the DFA = 3 + 1 = 4.

It suggests that minimized DFA will have 4 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • abb
  • aabb
  • ababb
  • abbabb

 

Step-03:

 

The required DFA is-

 

Problem-03:

 

Draw a DFA for the language accepting strings ending with ‘abba’ over input alphabets ∑ = {a, b}

 

Solution-

 

Regular expression for the given language = (a + b)*abba

 

Step-01:

 

  • All strings of the language ends with substring “abba”.
  • So, length of substring = 4.

 

Thus, Minimum number of states required in the DFA = 4 + 1 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • abba
  • aabba
  • ababba
  • abbabba
  • abbaabba

 

Step-03:

 

The required DFA is-

 

 

Problem-04:

 

Draw a DFA for the language accepting strings ending with ‘0011’ over input alphabets ∑ = {0, 1}

 

Solution-

 

Regular expression for the given language = (0 + 1)*0011

 

Step-01:

 

  • All strings of the language ends with substring “0011”.
  • So, length of substring = 4.

 

Thus, Minimum number of states required in the DFA = 4 + 1 = 5.

It suggests that minimized DFA will have 5 states.

 

Step-02:

 

We will construct DFA for the following strings-

  • 0011
  • 00011
  • 000011
  • 0010011
  • 00110011

 

Step-03:

 

The required DFA is-

 

 

Also Read- Converting DFA to Regular Expression

 

To gain better understanding about Construction of DFA,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Construction of DFA | Type-02 Problems

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Functional Dependency in DBMS

Database Management System

Functional Dependency-

 

In any relation, a functional dependency α → β holds if-

Two tuples having same value of attribute α also have same value for attribute β.

 

Mathematically,

If α and β are the two sets of attributes in a relational table R where-

  • α ⊆ R
  • β ⊆ R

Then, for a functional dependency to exist from α to β,

If t1[α] = t2[α], then t1[β] = t2[β]

 

α β
t1[α] t1[β]
t2[α] t2[β]
……. …….

 

fd : α → β

 

Types Of Functional Dependencies-

 

There are two types of functional dependencies-

 

 

  1. Trivial Functional Dependencies
  2. Non-trivial Functional Dependencies

 

1. Trivial Functional Dependencies-

 

  • A functional dependency X → Y is said to be trivial if and only if Y ⊆ X.
  • Thus, if RHS of a functional dependency is a subset of LHS, then it is called as a trivial functional dependency.

 

Examples-

 

The examples of trivial functional dependencies are-

  • AB → A
  • AB → B
  • AB → AB

 

2. Non-Trivial Functional Dependencies-

 

  • A functional dependency X → Y is said to be non-trivial if and only if Y ⊄ X.
  • Thus, if there exists at least one attribute in the RHS of a functional dependency that is not a part of LHS, then it is called as a non-trivial functional dependency.

 

Examples-

 

The examples of non-trivial functional dependencies are-

  • AB → BC
  • AB → CD

 

Inference Rules-

 

Reflexivity-

If B is a subset of A, then A → B always holds.

 

Transitivity-

If A → B and B → C, then A → C always holds.

 

Augmentation-

If A → B, then AC → BC always holds.

 

Decomposition-

If A → BC, then A → B and A → C always holds.

 

Composition-

If A → B and C → D, then AC → BD always holds.

 

Additive-

If A → B and A → C, then A → BC always holds.

 

Rules for Functional Dependency-

 

Rule-01:

 

A functional dependency X → Y will always hold if all the values of X are unique (different) irrespective of the values of Y.

 

Example-

 

Consider the following table-

 

A B C D E
5 4 3 2 2
8 5 3 2 1
1 9 3 3 5
4 7 3 3 8

 

The following functional dependencies will always hold since all the values of attribute ‘A’ are unique-

  • A → B
  • A → BC
  • A → CD
  • A → BCD
  • A → DE
  • A → BCDE

In general, we can say following functional dependency will always hold-

 

A → Any combination of attributes A, B, C, D, E

 

Similar will be the case for attributes B and E.

 

Rule-02:

 

A functional dependency X → Y will always hold if all the values of Y are same irrespective of the values of X.

 

Example-

Consider the following table-

 

A B C D E
5 4 3 2 2
8 5 3 2 1
1 9 3 3 5
4 7 3 3 8

 

The following functional dependencies will always hold since all the values of attribute ‘C’ are same-

  • A → C
  • AB → C
  • ABDE → C
  • DE → C
  • AE → C

 

In general, we can say following functional dependency will always hold true-

 

Any combination of attributes A, B, C, D, E → C 

 

Combining Rule-01 and Rule-02 we can say-

 

In general, a functional dependency α → β always holds-

If either all values of α are unique or if all values of β are same or both.

 

Rule-03:

 

For a functional dependency X → Y to hold, if two tuples in the table agree on the value of attribute X, then they must also agree on the value of attribute Y.

 

Rule-04:

 

For a functional dependency X → Y, violation will occur only when for two or more same values of X, the corresponding Y values are different.

 

Next Article- Equivalence of Functional Dependencies

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.