Grammars and Regular Expressions a) Design a grammar which generates the languag
ID: 3906648 • Letter: G
Question
Grammars and Regular Expressions
a) Design a grammar which generates the language: { (a | b)2ncn | n is a positive integer }
Example: abc, bbbbcc, abaabbccc
b) Design a grammar which generates the language which is composed of substrings of either 0s and 2s or 0s and 3s, and the substrings are divided by 1s. A substring can be empty. (What is not allowed is substrings with 2s next to substrings with 3s without a 1 separator.)
Example: 02, 02120, 03310211
Not allowed: 02003
c) Write a regular expression (using only the constructs that are part of the formal definition of a regular expression) which matches only strings composed of 0s and 1s that have both 000 and 111 in them (in any order).
Explanation / Answer
a)
S -> AASc| AAc
A -> a | b
Explanation
S is to have 2 A's for one c at the end which makes it 2n for n
b)
S -> A | DBAC
D -> DBA | A
C -> 1C | epsilon
B -> 1B | 1
A -> E | F
E -> 0E | 2E | 0 | 2
F -> 0F | 3F | 0 | 3
Explanation
A is to have either E or F
E is for 0s and 2s
F is for 0s and 3s
C is there in case if there are trailing zeros
B is for 1/more number of 1's to separate E and F
c)
(0+1)*000(0+1)*111(0+1)* + (0+1)*111(0+1)*000(0+1)*
Explanation
First one is to have 000 followed by 111
Second one is to have 111 followed by 000
Any number of 0's or 1's can come in between