Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    FLAT Unit-3 Part2

    Uploaded by

    Gopl Kuppa
    Context-free languages are closed under union, concatenation, and Kleene star operation. They are not closed under intersection or complement. The pumping lemma can be used to prove that a language is not context-free by showing that any string of length greater than the pumping length cannot be pumped in a way that keeps the string in the language.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    FLAT Unit-3 Part2

    Uploaded by

    Gopl Kuppa
    15 views9 pages
    Context-free languages are closed under union, concatenation, and Kleene star operation. They are not closed under intersection or complement. The pumping lemma can be used to prove that a language is not context-free by showing that any string of length greater than the pumping length cannot be pumped in a way that keeps the string in the language.

    Original Description:

    FLAT Unit 3

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Context-free languages are closed under union, concatenation, and Kleene star operation. They are not closed under intersection or complement. The pumping lemma can be used to prove that a language is not context-free by showing that any string of length greater than the pumping length cannot be pumped in a way that keeps the string in the language.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    15 views9 pages

    FLAT Unit-3 Part2

    Uploaded by

    Gopl Kuppa
    Context-free languages are closed under union, concatenation, and Kleene star operation. They are not closed under intersection or complement. The pumping lemma can be used to prove that a language is not context-free by showing that any string of length greater than the pumping length cannot be pumped in a way that keeps the string in the language.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 9

    2. List and explain the closure properties of regular grammar.

    [June/July – 2022, Set-2]


    [Remembering ]

    Context Free Languages (CFLs) are accepted by pushdown automata. Context free languages
    can be generated by context free grammars, which have productions (substitution rules) of the
    form :

    A -> ? (where A ? N and ? ? (T ? N)* and N is a non-terminal and T is a terminal)

    Properties of Context Free Languages


    Context-free languages are closed under −

     Union
     Concatenation
     Kleene Star operation

    Union
    Let L1 and L2 be two context free languages. Then L1 ∪ L2 is also context free.
    Example
    Let L1 = { anbn , n > 0}. Corresponding grammar G1 will have P: S1 → aAb|ab
    Let L2 = { cmdm , m ≥ 0}. Corresponding grammar G2 will have P: S2 → cBb| ε
    Union of L1 and L2, L = L1 ∪ L2 = { anbn } ∪ { cmdm }
    The corresponding grammar G will have the additional production S → S1 | S2

    Concatenation
    If L1 and L2 are context free languages, then L1L2 is also context free.
    Example
    Union of the languages L1 and L2, L = L1L2 = { anbncmdm }
    The corresponding grammar G will have the additional production S → S1 S2

    Kleene Star
    If L is a context free language, then L* is also context free.
    Example
    Let L = { anbn , n ≥ 0}. Corresponding grammar G will have P: S → aAb| ε
    Kleene Star L1 = { anbn }*
    The corresponding grammar G1 will have additional productions S1 → SS1 | ε

    Context-free languages are not closed under −

     Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily


    context free.
     Intersection with Regular Language − If L1 is a regular language and L2 is a context free
    language, then L1 ∩ L2 is a context free language.
     Complement − If L1 is a context free language, then L1’ may not be context free.
    3. What is pumping lemma? Explain its closure properties? [June/July – 2022, Set-3]
    [Remembering ]

    Pumping Lemma

    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.

    You might also like