TC

  • \{a^nb^nc^n\mid n\in \mathbb N\} is not context-free
  • CFL is closed under intersection with regular languages
  • exercises on CFL (Homework 2)

March 24, 2026

Given A=\{a^ib^jc^k \mid i=j+k\}, B=\{a^ib^jc^k \mid j=i+k\}, C=\{a^ib^jc^k \mid k=i+j\}, and \small G_1: \begin{cases} S \longrightarrow S_1 S_2 \\ S_1 \longrightarrow aS_1b \mid \lambda \\ S_2 \longrightarrow bS_2c \mid \lambda \end{cases} \quad G_2: \begin{cases} S \longrightarrow aSc \mid S' \\ S' \longrightarrow bS'c \mid \lambda \\ \end{cases} \quad G_3: \begin{cases} S \longrightarrow aSc \mid S' \\ S' \longrightarrow aS'b \mid \lambda \\ \end{cases} Which of the following options is correct?

  1. A = \mathscr L(G_1), B = \mathscr L(G_2), C = \mathscr L(G_3).
  2. A = \mathscr L(G_3), B = \mathscr L(G_1), C = \mathscr L(G_2).
  3. A = \mathscr L(G_2), B = \mathscr L(G_3), C = \mathscr L(G_1).
  4. A = \mathscr L(G_3), B = \mathscr L(G_2), C = \mathscr L(G_1).

Given the following grammars: \small G_1: \begin{cases} S \longrightarrow A B\\ A \longrightarrow Aaa \mid a \mid \lambda\\ B \longrightarrow Baa \mid aa \mid \lambda \end{cases} \quad G_2: \begin{cases} S \longrightarrow A \mid B \mid \lambda \\ A \longrightarrow Aaa \mid a \\ B \longrightarrow Baa \mid aa \end{cases}

  1. \mathscr L(G_1) = \mathscr L(G_2) and exactly one is ambiguous.
  2. \mathscr L(G_1) \ne \mathscr L(G_2) and exactly one is ambiguous.
  3. \mathscr L(G_1) = \mathscr L(G_2) and both are ambiguous.
  4. \mathscr L(G_1) \ne \mathscr L(G_2) and both are ambiguous.

Consider the following grammar with 5 productions: \small \begin{array}{rl} S &\rightarrow A\,B \\ A &\rightarrow a\,A \mid \lambda \\ B &\rightarrow b\,B \mid \lambda\end{array}.

How many productions has the grammars obtained by depurating it?

  1. 10
  2. 11
  3. 12
  4. 13

There is no need to define a new initial symbol, but you need to remove \lambda-productions and unary productions.

We want to show that L= \{a^mb^nc^md^n \mid m,n \geq 0\} is not context-free using directly the pumping lemma for CFL. Given the pumping length N, we choose a word w to apply the lemma.

Which of the following choices has some hope to make the rest of the argument correct?

  1. w = abcd.
  2. w = a^N bc^N d.
  3. w = ab^N cd^N.
  4. w = a^N b^N c^N d^N.

Theory bits

  • \{a^nb^nc^n\mid n\in \mathbb N\} is not context-free
  • Pumping lemma for CFL

Theorem 1 If L is a CFL and L' is regular, then L\cap L' is a CFL, i.e. CFL are closed under intersection with regular languages.

Proof sketch 1: via PDAs and the cross product construction

Proof sketch 2: G=(V,\Sigma,\mathcal R,S) grammar in Chomsky Normal Form that does not generate \lambda, M=(Q,\Sigma,\delta,q_0,\{q_F\}) a DFA with a single final state. The grammar for \mathscr{L}(G)\cap \mathscr{L}(M) is G'=(V',\Sigma,\mathcal R',S'), where \begin{align*} V'=&\{\langle q,A,r\rangle \mid q,r\in Q,A\in V\} \\ S'=&\langle q_0,S,q_F\rangle \\ \mathcal R' = &\{\langle q,A,r\rangle \to t \mid A\to t \in \mathcal R \text{ with } t\in \Sigma\cup\{\lambda\} \land \delta(q,t)=r \} \cup\\ &\{\langle q,A,r\rangle \to \langle q,B,s\rangle\langle s,B,r\rangle \mid A\to BC \in \mathcal R \land q,s,r\in Q \} \end{align*}

\langle q,A,r\rangle generates the strings w that are generated by A in G such that when M reads w starting from state q, it ends in state r.

  • if \mathscr{L}(M)=\emptyset, easy (check)
  • if M has more than one accept state, write it as a finite union of DFAs with a single accpet state
  • if \lambda\in \mathscr{L}(G)\cap\mathscr{L}(M), add to \mathcal R' the production \langle q_0,S,q_F\rangle \to \lambda

exercises of Homework 2

Tomorrow
  • first hour lab on CFG/DFAs/exams (with David)
  • second hour exercises from Homework 2 (with me)
Partial Exam 1
  • on April 8, covers the material seen until now
  • format of the exam:
    • 3 hours
    • 4 exercises on RACSO (2 DFAs, 2 CFGs, 1 point each)
    • 8 “quiz” exercises (.5 points each)
    • 2 open questions (1 point each)
  • If you send emails with questions/doubts after April 3 I might not be able to answer in time for the partial exam.