Pumping Lemma

Lemma: (Pumping Lemma)
If L is a regular language, then there exists a positive integer p (the pumping length) such that every string s ∈
 L,|s | ≥p, can be partitioned into three pieces,s=xyz, such that the following conditions hold:
1.|y| > 0,
2.|xy| ≤p, and
3.for each i ≥0, xyiz




Standard Example:

1.L={anbn | n=0}is not regular.
2.L={1n | n is a prime number}is not regular.
3.L={0i1j| i > j}is not regular.

Comments

Popular posts from this blog

JDBC Hive Connection fails : Unable to read HiveServer2 uri from ZooKeeper

Access Kubernetes ConfigMap in Spring Boot Application

Developing Custom Processor in Apache Nifi