Context Free Grammar
S -> XB
X -> aXa | b
B -> bB | epsilon
Explanation
Y is to have {bk | k >= 0}
X is for {ajbaj | j>=0}
Chomsky Normal Form
S -> XB | CA | b
X -> CA | b
B -> DB | b
A -> a
C -> AX
D -> b
-- Please up vote
Write a grammar in Chomsky Normal Form whose language is {w € {a,b}* | w =...
Question 8 10 pts Let S = {a,b,c}. Write a grammar that generates the language: L = {(ac)"6n+1w: n > 0, W € 2*, W contains the substring acb}
13.) Write a grammar for the language consisting of strings that have n copies of the letter a followed by one more number of copies of the letter b, where n>0. For example, the strings abb, aaaabbbbb, and aaaaaaaabbbbbbbbb are in the language but a, ab, ba, and aaabb are not. Answer the aaaaaabbbbbbbh are in the languagebr 14.) Draw parse trees for the sentences abb and aabbb, as derived from the grammar of Problem 13. Answer:
4. Construct a grammar over {a, b} whose language is {a"b"|0sn<m<3n}.
number 2 only please, could not take a smaller picture.
2 Find a regular grammar that generates the language • {w | We{0,1}* , [w] >= 4; w starts with 1 and ends with 10 or 01). 3 Find a regular expression that denotes the language accepted by the below finite automaton. 0 E B 0,1 1 D 0 с F
4. Fill out the following blanks to make it a context-free grammar for the given language: { an+1 bn | n >= 0}{a2nbn2 | n >= 0 } (8 points) S + AB, A → B
Construct a context-free grammar for the language L={ab'ab'an> 1}.
Construct a context-free grammar for the language L={ ab"ab'an> 1}.
) Construct a context-free grammar for the language L={ ab”ab”a | n> > 1}.
Construct a context-free grammar for the language L={ ab”ab”a | n> 1}.
Let G = (V, S, R, S) be a grammar with V = {Q, R, T}; { = {q, r,ts}; and the set of rules: SQ Q→ RqT RrrT QQr T>t | StT b. (15) Convert G to Chomsky normal form.