Regular Closure of CFLs

COMP218 Lectures 2021-11-19

Intersection of Context-Free & Regular Languages

The intersection of a CFL and a regular language:

\[L_1\cap L_2\]

is context free.

Combining the Languages

To combine the CFL $M_1$ (a PDA) and regular language $M_2$ (a DFA) we can use the following transformations:

• Transition 1

    stateDiagram
  	
    state M1 {
    direction lr
    q1 --> q2:a, b/c
    }
    state M2 {
    direction lr
    p1 --> p2:a
    }
    state M {
    direction lr
    q1,p1 --> q2,p2:a, b/c
    }
    M1 --> M
    M2 --> M
  

• Transition 2

    stateDiagram
  	
    state M1 {
    direction lr
    q1 --> q2:epsilon, b/c
    }
    state M2 {
    direction lr
    p1
    }
    state M {
    direction lr
    q1,p1 --> q2,p1:epsilon, b/c
    }
    M1 --> M
    M2 --> M
  

• Initial State

    stateDiagram
  	
    state M1 {
    direction lr
    [*] --> q0
    }
    state M2 {
    direction lr
    [*] --> p0
    }
    state M {
    direction lr
    [*] --> q0,p0
    }
    M1 --> M
    M2 --> M
  

• Final States

    stateDiagram
  	
    state M1 {
    direction lr
    q1 --> [*]
    }
    state M2 {
    direction lr
    p1 --> [*]
    p2 --> [*]
    }
    state M {
    direction lr
    q1,p1 --> [*]
    q1,p2 --> [*]
    }
    M1 --> M
    M2 --> M
  

General Rules

• $M$ simulates in parallel $M_1$ and $M_2$.
• $M$ accepts string $w$ if and only if:
  • $M_1$ accepts string $w$ and,
  • $M_2$ accepts string $w$

  This is to say that $L(M)=L_1\cap L_2$.

• As $M$ is a PDA then the final language ($L(M)=L_1\cap L_2$) is context-free.

Applications of Regular Closure

You can use combinations of regular and context-free closures to prove that a language is context-free:

• If we can make a language as an intersection of context-free and regular languages, then we know that is it context-free.

  This allows you to prove that the language is context free without having to build a grammar.

There is an example of this at the end of the lecture video.