Design and draw the diagram of a push-down automaton for each of the languages below. Make...

 

Transcribed Image Text:

Design and draw the diagram of a push-down automaton for each of the languages below. Make sure to mark the initial state and the final states in your diagrams. If you are unable to find a correct solution, then drawing a PDA that recognizes a similar language may earn you partial points. Note: If you are unable to draw a diagram for some reason, you can write down the transi- tions in their formal form. A. (10 pts) {wcw w {ab}* A w is even A w contains no consecutive a's} Recall that a string v contains consecutive a's if the string aa is a substring of v. (Hint: Enforcing the last two restrictions in different parts of the machine might make your job easier, though not required.) B. (10 pts) {ab | m, n, k 0 ^ n = m + k} Design and draw the diagram of a push-down automaton for each of the languages below. Make sure to mark the initial state and the final states in your diagrams. If you are unable to find a correct solution, then drawing a PDA that recognizes a similar language may earn you partial points. Note: If you are unable to draw a diagram for some reason, you can write down the transi- tions in their formal form. A. (10 pts) {wcw w {ab}* A w is even A w contains no consecutive a's} Recall that a string v contains consecutive a's if the string aa is a substring of v. (Hint: Enforcing the last two restrictions in different parts of the machine might make your job easier, though not required.) B. (10 pts) {ab | m, n, k 0 ^ n = m + k}