flat:pummping lemma with examples

heorem

Let L be a regular language. Then there exists a constant ‘c’ such that for every string w in L −
|w| ≥ c
We can break w into three strings, w = xyz, such that −
  • |y| > 0
  • |xy| ≤ c
  • For all k ≥ 0, the string xykz is also in L.

Applications of Pumping Lemma

Pumping Lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular.
  • If L is regular, it satisfies Pumping Lemma.
  • If L does not satisfy Pumping Lemma, it is non-regular.

Method to prove that a language L is not regular

  • At first, we have to assume that L is regular.
  • So, the pumping lemma should hold for L.
  • Use the pumping lemma to obtain a contradiction −
    • Select w such that |w| ≥ c
    • Select y such that |y| ≥ 1
    • Select x such that |xy| ≤ c
    • Assign the remaining string to z.
    • Select k such that the resulting string is not in L.
Hence L is not regular.
Problem
Prove that L = {aibi | i ≥ 0} is not regular.
Solution −
  • At first, we assume that L is regular and n is the number of states.
  • Let w = anbn. Thus |w| = 2n ≥ n.
  • By pumping lemma, let w = xyz, where |xy| ≤ n.
  • Let x = ap, y = aq, and z = arbn, where p + q + r = n, p ≠ 0, q ≠ 0, r ≠ 0. Thus |y| ≠ 0.
  • Let k = 2. Then xy2z = apa2qarbn.
  • Number of as = (p + 2q + r) = (p + q + r) + q = n + q
  • Hence, xy2z = an+q bn. Since q ≠ 0, xy2z is not of the form anbn.
  • Thus, xy2z is not in L. Hence L is not regular.

     Pumping Lemma for CFG
    If L is a context-free language, there is a pumping length p such that any string w ∈ L of length ≥ p can be written as w = uvxyz, where vy ≠ ε, |vxy| ≤ p, and for all i ≥ 0, uvixyiz ∈ L.

    Applications of Pumping Lemma

    Pumping lemma is used to check whether a grammar is context free or not. Let us take an example and show how it is checked.

    Problem

    Find out whether the language L = {xnynzn | n ≥ 1} is context free or not.

    Solution

    Let L is context free. Then, L must satisfy pumping lemma.
    At first, choose a number n of the pumping lemma. Then, take z as 0n1n2n.
    Break z into uvwxy, where
    |vwx| ≤ n and vx ≠ ε.
    Hence vwx cannot involve both 0s and 2s, since the last 0 and the first 2 are at least (n+1) positions apart. There are two cases −
    Case 1 − vwx has no 2s. Then vx has only 0s and 1s. Then uwy, which would have to be in L, has n 2s, but fewer than n 0s or 1s.
    Case 2 − vwx has no 0s.
    Here contradiction occurs.
    Hence, L is not a context-free language.

Comments

Post a Comment

Popular posts from this blog

Intelligent Agents(Algorithms for Intelligent Systems)

    Unit II: Intelligent Agents   Intelligent Agents: Agents and Environments, The Concept of Rationality, The Nature of Environments (PEAS), The Structure of Agents: Simple Reflex Agents, Model-Based Reflex Agents, Goal-Based Agents, Utility-Based agents, Learning Agents. Agents and Environments: Agent An  agent  is an entity that perceives its environment through sensors and acts upon that environment through actuators. Agents can be anything from simple programs to complex systems like robots or humans. The key characteristic of an agent is its ability to take actions based on its perceptions to achieve specific goals. Environment The  environment  is the external context or world in which the agent operates. It includes everything the agent can perceive and interact with. The environment provides the agent with inputs (percepts) and receives outputs (actions) from the agent. Example Consider a  self-driving car : ...
Read more

2D-Transformations

Image
Transformation means changing some graphics into something else by applying rules. We can have various types of transformations such as translation, scaling up or down, rotation, shearing, etc. When a transformation takes place on a 2D plane, it is called 2D transformation. Transformations play an important role in computer graphics to reposition the graphics on the screen and change their size or orientation. Homogenous Coordinates To perform a sequence of transformation such as translation followed by rotation and scaling, we need to follow a sequential process − Translate the coordinates, Rotate the translated coordinates, and then Scale the rotated coordinates to complete the composite transformation. To shorten this process, we have to use 3×3 transformation matrix instead of 2×2 transformation matrix. To convert a 2×2 matrix to 3×3 matrix, we have to add an extra dummy coordinate W. In this way, we can represent the point by 3 numbers instead of 2 numbers, wh...
Read more

3D-Transformations(Including projections)

Image
In the 2D system, we use only two coordinates X and Y but in 3D, an extra coordinate Z is added. 3D graphics techniques and their application are fundamental to the entertainment, games, and computer-aided design industries. It is a continuing area of research in scientific visualization. Furthermore, 3D graphics components are now a part of almost every personal computer and, although traditionally intended for graphics-intensive software such as games, they are increasingly being used by other applications. Parallel Projection Parallel projection discards z-coordinate and parallel lines from each vertex on the object are extended until they intersect the view plane. In parallel projection, we specify a direction of projection instead of center of projection. In parallel projection, the distance from the center of projection to project plane is infinite. In this type of projection, we connect the projected vertices by line segments which correspond to connections o...
Read more