5. (12 points) Design PDAs for the following languages. For cach language, you are asked to...

Transcribed Image Text:

5. (12 points) Design PDAs for the following languages. For cach language, you are asked to first give an informal description of your PDA and then give the state diagram. (a) {01/0 |i,j1} (b) {abick | i-jor j = k, where i, j, k 0}. Note that this is not the same language as that in Question 3(c). 6. (6 points) In class, we studied a method to convert a CFG to an equivalent PDA. Following that method, convert the following CFG to an equivalent PDA. EE+T T TTXF|F F (E) | a 7. (12 points) Using the CFL pumping lemma to prove that the following languages are not context free. (a) {w w *, and in w, the number of a's equals the number of b's and the number of c's equals the number of d's }, where = {a,b,c,d}. For example, adbc and adcdbe are in the language, but adbca is not. (b) {abcm |0 mn} 5. (12 points) Design PDAs for the following languages. For cach language, you are asked to first give an informal description of your PDA and then give the state diagram. (a) {01/0 |i,j1} (b) {abick | i-jor j = k, where i, j, k 0}. Note that this is not the same language as that in Question 3(c). 6. (6 points) In class, we studied a method to convert a CFG to an equivalent PDA. Following that method, convert the following CFG to an equivalent PDA. EE+T T TTXF|F F (E) | a 7. (12 points) Using the CFL pumping lemma to prove that the following languages are not context free. (a) {w w *, and in w, the number of a's equals the number of b's and the number of c's equals the number of d's }, where = {a,b,c,d}. For example, adbc and adcdbe are in the language, but adbca is not. (b) {abcm |0 mn}

Answer rating: 100% (QA)

5 Design PDAs for the following languages For each language you are asked to first give an informal description of your PDA and then give the state diagram a The language 010 ij 1 consists of strings ... View the full answer