Grammars and Regular Expressions a) Design a grammar which generates the languag

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

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.