Question

Models of Languages and Computations

In the following, assume the accepting criteria for PDAs is by final state. Let
L = n > m > 0.
1.Give two PDAs P1, P2 that recognize L such that
(a) P1’s set of states is disjoint from P2’s set of states, and
(b) PDA P3 na¨ıvely constructed by adding ϵ transitions from the accepting states of P1 to the initial
state of P2 does not recognize L ◦ L.
2. Give a correct PDA construction for recognizing L ◦ L, using your P1, P2 above

Answer 1

The student is asked to construct two PDAs, P1 and P2, for recognizing the language L and then to correctly construct a PDA for recognizing L concatenated with itself, without directly transitioning between P1 and P2.

Step-by-step explanation:

The question deals with constructing two Pushdown Automata (PDAs), P1 and P2, which recognize the language L = 0^n1^m . Additionally, it requires a method to correctly construct a PDA that recognizes the concatenation of the language with itself, L ◦ L, using the previously defined P1 and P2.

For P1 and P2, we need to ensure they have disjoint state sets, which means they shouldn't have any shared states. A possible configuration for P1 and P2 can be:

• P1 has states Q1, and transitions that read 0, push it to the stack, then read 1 and pop for every matched 1, accepting if there are more 0s than 1s.
• P2 has states Q2, completely separate from Q1, and functions similarly to P1 but operates independently.

Constructing a naive PDA, P3, simply by adding ϵ transitions from the accepting states of P1 to the initial state of P2 would not work for L ◦ L because it would allow for the recognition of strings that do not fit the form, such as alternating 0s and 1s.

To correctly construct a PDA that recognizes L ◦ L, one can construct P3 by making sure it only transitions from the accepting state of P1 to the initial state of P2 on reading at least one additional 0. This ensures that the next sequence of 0s and 1s also adheres to the same relationship as defined in L.