Tuesday, December 4, 2012

Regular Language Examples

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.} 

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)