Assignment 6

1. Describe a PDA and a CFG for the language \(A=\left\{b^ia^jb^ka^jb^l \mid j > 0,\, i,k,l\geq 0 \right\}\)

2. Consider the language \(A\) of all words in \(\Sigma=\{a,b\}\) such that every prefix of \(w\) has at least as many \(a\)’s as \(b\)’s. Construct a PDA for this language. As extra credit, also construct a CFG for it.

3. This problem concerns the language \(C = A/B =\{w\mid wx\in A\textrm{ for some }x\in B\}\). In other words a string is in \(C=A/B\) if it can be extended to a string in \(A\), where the extension belongs to \(B\). This part has an easy question for you, the next part will be more challenging. There is an obvious relation between the languages \(CB\) (concatenation of \(C\) and \(B\)) and \(A\) (one is a subset of the other). Which relation is that?

4. In this problem we will sketch the proof of the following fact: If \(A\) is a context-free language, and \(B\) is regular, then \(A/B\) is context-free. You may want to think about it on your own first, get a bit of a feel for the question before reading on.

   We will outline the proof. It is your assignment to provide the details. Assume \(P\) is a PDA for \(A\), and \(D\) is a DFA for \(B\). We will construct a PDA \(O\) for \(A/B\).

   • The states of \(O\) are pairs of states from \(P\) and \(D\), i.e. \(Q_O = Q_P\times Q_D\). So at any given point a state in \(O\) keeps track of some state in \(P\) and some state in \(D\).
   • You will need to figure out the start state of \(O\), though nothing fancy is needed here.
   • The stack alphabet for \(O\) is the same as the one for \(P\). Any moves we take from \(P\), we will update our stack the same way they would.
   • You will need to formally define the transitions in \(O\). The idea is as follows:
     • As long as we have not moved in the DFA yet, i.e. as long as the state we are in in \(O\) is a pair that contains the start state of \(D\), then our PDA has two types of choices:
       1. It can take a valid step from \(P\), and not move in \(D\). This corresponds to us still trying to recognize the “\(w\)” part of the \(wx\) in the definition of \(A/B\).
       2. It can take a valid step in \(P\) that consumes some input, and take a move in \(D\) corresponding to that same input. This commits the PDA to stop working on the \(w\) part and start working on the \(x\) part.
     • Once we have moved \(D\), so we are no longer on its start state, our transitions become more limited. Essentially you only move if you can do it as an \(\epsilon\)-move in the PDA, or if it is a simultaneous move in both. At this point we are tracing the \(x\) part in the \(wx\) from the definition.
       1. We can make a valid step from \(P\) that does NOT consume any input, and stay in the same state in \(D\).
       2. We can make a valid step from \(P\) that consumes an input, then move in \(D\) using that same input.
   • If we make our accept states those pairs that correspond to both an accept state in \(P\) and an accept state in \(D\), this recognizes a different language. Describe that language.
   • Describe which states in \(O\) we should call accept states, if we want to obtain \(A/B\).
   • Sketch a proof of why/how this PDA achieves the desired objective of recognizing the language \(A/B\).

5. If \(A\) and \(B\) are languages, we define a new language \(C=A\diamond B =\{xy\mid x\in A,\, y\in B\, |x|=|y|\}\), i.e. the new language is formed out of the contatenation of a string from \(A\) with a string from \(B\), whenever those strings have the same length. Show that if \(A\) and \(B\) are regular languages, then \(A\diamond B\) has to be context-free. (Hint: Construct the PDA for \(A\diamond B\). Start with DFAs for \(A\) and for \(B\), use the union of their states, with some epsilon transitions thrown in, and maybe extra start/end states for stack cleanup. Use the stack to keep track of how many elements you’ve seen in \(x\), then count them backwards in \(y\).).

Extra credit problem: If \(C=A/B\) as above, part 3 already asked you to show that one of \(CB\) and \(A\) is a subset of the other. As an extra credit problem, determine the status of the other direction: Are \(A\) and \(CB\) always equal? Either prove that they are always equal or provide a counterexample of languages \(A\) and \(B\) where if we define \(C=A/B\) then \(A\) and \(CB\) are not equal.

Extra credit problem 2: What about \(A\diamond B\) when \(A\) is a CFL and \(B\) is regular?