1. Build PDA to generate all strings of the form 0n12n+3 where n>=0 2. Build CFG to generate all strings of the form 0n12n+3 where n>=0 3. Build PDA to generate all strings of the form 0n1 n where n is even 4. Build CFG to generate all strings of the form 0n1 n where n is even 5. Build PDA to generate all strings of the form 1 n 0 m, where m and n are even, and m>n 6. Build CFG to generate all strings of the form 1 n 0 m 1 n, where m and n are greater or equal to 0. 7. Build PDA to generate all strings of the form w11, where w is a palindrome containing 1's and 0's. For example, the following strings should be generated: • 01011 (010 is a palindrome, and 11 is the ending) • 1101111 (11011 is a palindrome, and 11 is the ending) • 01011 (010 is a palindrome, and 11 is the ending) 8. Build CFG to generate all strings of the form w11, where w is a palindrome containing 1's and 0's. 9. Build PDA which generates all non-empty strings with equal number of 1’s and 0’s \ 10. Please provide an example of \ CFG for Natural Language to derive the following sentence: • mary reads a strange book
1. Build PDA to generate all strings of the form 0n12n+3 where n>=0
2. Build CFG to generate all strings of the form 0n12n+3 where n>=0
3. Build PDA to generate all strings of the form 0n1 n where n is even
4. Build CFG to generate all strings of the form 0n1 n where n is even
5. Build PDA to generate all strings of the form 1 n 0 m, where m and n are even, and m>n
6. Build CFG to generate all strings of the form 1 n 0 m 1 n, where m and n are greater or equal to 0.
7. Build PDA to generate all strings of the form w11, where w is a palindrome containing 1's and 0's. For example, the following strings should be generated: • 01011 (010 is a palindrome, and 11 is the ending) • 1101111 (11011 is a palindrome, and 11 is the ending) • 01011 (010 is a palindrome, and 11 is the ending)
8. Build CFG to generate all strings of the form w11, where w is a palindrome containing 1's and 0's.
9. Build PDA which generates all non-empty strings with equal number of 1’s and 0’s \
10. Please provide an example of \ CFG for Natural Language to derive the following sentence: • mary reads a strange book
“Since you have posted a question with multiple sub-parts, we will solve first three sub- parts for you. To get the remaining sub-part solved please repost the complete question and mention the sub-parts to be solved.”
CFG: -
A Context Free Grammar (CFG) is a formal way of specifying a set of strings that can be generated from a given starting symbol. A CFG consists of a set of production rules, which define how the starting symbol can be replaced by other strings of symbols.
Step by step
Solved in 4 steps with 2 images
