441 views
1 1 vote

Give a context-free grammar for each of the following languages. Consider, Σ={0,1}.

A. The language of strings that start with 1

B. The language of strings of the form WWR 

C. The language of strings that contain the substring 001

D. The language {0n10n where n ≥ 0}

E. The language {0i1j where i ≤ j}

F. The language {1i01j01i+j}

G. The language {03nw12n where n ≥ 0 and w is a string that contains at least two 0’s}

H. The language {0i10j | i is a multiple of three where i, j ≥ 0}

I. The language {0i10 j | j = 2 + 3i where i, j ≥ 0}

J. The language {1i01j | j is a multiple of four or i = 3 + 2j where i, j ≥ 0}

Please log in or register to answer this question.

Position:
Show:

Related questions

1 1 vote
1 1 answer
1.4k
1.4k views
Garrett McClure asked Oct 14, 2017
1,440 views
Find a context-free grammar for the following language (with n ≥ 0, m ≥ 0):L = {anwwRbn : w ∈ {a, b} ∗ , n ≥ 1}.
0 0 votes
2 2 answers
2.4k
2.4k views
atulcse asked Jan 21, 2022
2,360 views
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
0 0 votes
0 0 answers
177
177 views
lambodar_pal asked Jul 27
177 views
The intersection of a context free language and a regular languagea)need not be regularb)need not be context freec) is always regulard) is always context free