Showing posts with label TOC-Finite Automata. Show all posts
Showing posts with label TOC-Finite Automata. Show all posts

Tuesday, December 4, 2012

Converting Regular Expression to NFA

No comments: Labels: , ,
We can convert a regular expression to NFA by METHOD OF DECOMPOSITION
Step 1: In this mechanism we need to take the given RE as a edge-label for the FA with 2 states: one is initial and other is final state i.e. we have to start a process with 2 state machine.
Read more »

Regular Language Examples

No comments: Labels: ,
Regular Language is a formal language which is accepted by a Finite State Machine (or Finite State Automata).

 'or'

 Regular Language is a formal language which can be generated by a regular expression.

 'or'

 Regular Language is a formal language which can be generated by a regular grammar.

 Note:-

  • The language which is not accepted by Finite Automata is known as non-regular language.
  • Every formal language must be regular or non-regular.
  • Every finite language is a regular language.
  • Every infinite language can be regular or non-regular.
  • Every non-regular language is infinite language.
Examples of Regular Language:
1. L = {0n | n= 2 or n=4}
2. L = {0m 1n| m=2n, m=n= 1, 2, 3}
3. L = {w Є ∑* | w=wR, |w|=3}
4. L = {an | n≥1}   
    - Even if it is an infinite language it is a regular language because it does not depend on any conditions.
5. L = {0m 1n| m+n=even no.} 
    - We can construct the FA for the above

Examples of Non-Regular Language:
1. L = {am bn| m = n, m and n ≥ 1}
2. L = {am bn| m > n, m and n ≥ 1}
3. L = {am bn| m < n, m and n ≥ 1}
4. L = {w Є ∑* | |w|a=|w|b}
5. L = {w Є ∑* | w= wR}
6. 5. L = {0m 1n| m.n=even no.} 

Finite State Machine that adds two integers

10 comments: Labels: ,

Q. Construct a finite-state machine or finite state automaton that adds two integers (using binary representation of integers).

Sol:
Finite Automata (FA) or Finite State Machine to add two integers can be constructed using two states:

· q0: Start state to represent carry bit is 0
·  q1: State to represent carry bit is 1


The inputs to FA will be pair of bits i.e. 00, 01, 10, and 11


The FA starts in state 1 (since carry is 0) and inputs a pair of bits. If the pair is 11, the FA outputs a 0 and switches to state 2 (since the carry is 1), where the next pair of bits is input and is added to a carry bit of 1.

Example: Consider the addition of 52 and 21
110100 - (binary representation of 52)
010101 - (binary representation of 21)

Since adding numbers is done from right to left, The first input symbol is 01, representing a 0 in the rightmost (binary) digit of 52 and a 1 in the rightmost digit of 21. The machine enters state  q0 (since there is no carry) and outputs a 1. The next input is 00 because both numbers have zero as the second  rightmost digit. The machine enters state q0 and outputs 0. The next input is 11. The machine enters state q1 (since the carry is 1) and outputs 0. Being in state q1 means that there is a carry from this position into the next. And the remaining bits can be worked out to get 1001001 (i.e. 73).
Subscribe to: Posts (Atom)