Question: Given grammar: S - > 0 S 1 | epsilon L ( G ) = { 0 ^ x 1 ^ x | x >

Given grammar: S ->0 S 1| epsilon L(G)={0^x 1^x | x >=0}
0s are followed by the same number of 1s and the shortest string is empty.
S =>0 S 1=>00 S 11=>000 S 111=>000111
Refer back to this grammar to answer Q1 and Q2.
Q1. My L(G)={0^x c 1^x | x >=0}
a. Describe the language in English without referring to x. Also state the shortest string. ?**?
b. Change the above grammar to generate this language. (a very minor change)?**?
Q2. My L(G)={0^x 1^x c 0^y 1^y | x >=0 and y >=0}
a. Describe the language in English without referring to x. Also state the shortest string. ?**?
b. Change the above grammar to generate this language. (This is NOT S ->0 S 10 S 1)?**?
Q3. What is L(G)of the following grammar?
Give a set former description as done above for the following. ?**?
S ->0 B 1 HINT: At least how many 1s???
B ->1 B
B ->1

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!