Tuesday, February 8, 2022

Pumping Lemma for Regular Languges


Pumping lemma used to show that language is not regular. 

What is pumping?

for regular expression

r = (a u b) (abb)* (bba u bbb), the string w= babbbbb pumps because we may decompose w into three sub strings.

w= b.  abb.  bbb

such that  b(abb)i bbb is represented by r, for every i>= 0.

in this DFA.,


the string aaabab= aa. aba.b pumps because of the cycle that the aba follows.


Suppose L is a regular Language., the there exists an integer k such that for all strings z belongs to L. , satisfying |z|>=k., we can write z= uvw where

|v| >= 1

|uv| <=k

u vw  belongs to L, for all i>=0.


No comments:

Post a Comment

A simple Java program to find the inverse of a given matrix

  import java.util.Scanner; public class MatrixInverse { public static void main (String[] args) { Scanner scanner =...