asked on

a context free grammar solution

I was studying this pdf :
http://staffwww.dcs.shef.ac.uk/people/J.Marshall/alc/studyguides/Selected_Solutions_2.pdf
But i think there is some mistake or lacking on somewhere.
I uploaded the related part's photo.
In, i < j + k part , we did S4->S5c
However in our cfg , "bb" is also possible possible and it must exist in the i<j+k part , however with the given solution , we cannot reach "bb" . Thus , there is some lacking in the solution , i think.
Am i right?
question.png

GwynforWeb

I believe you are correct. The answer needs S0 -> S6 then

S6 -> S6b (by definition)
-> S6bb (by S6 -> S6b)
->bb (by S6 -> e )

codeBuilder

ASKER

OK. Thanks.

GwynforWeb

You are correct, as it is you will always get a c in the string. There are different ways of fixing the grammar up. This probably the simplest.

The relationship

S4 -> S5c

needs to be changed to

S4 -> S5b | S5c

It is then

S0 -> S4 -> S5b -> S6b -> S6bb -> bb

codeBuilder

ASKER

If you do in that way S4 -> S5b | S5c, you say that b is the last and c can come before b. Thus , it fails.
Here , the problem is any number of b's.
Thus, WE should do as in the below , i think

S7-> S7b| e
and S0 -> S1 | S4 | S7

ASKER CERTIFIED SOLUTION

GwynforWeb

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

codeBuilder

ASKER

I find different types of cfg problems from a midterm(2nd question) such that:
midterm

or similar questions from a homework:
Give context-free grammars generating the following languages:

(a) { w#x | wR is a substring of x, for w,x ¿ { 0, 1 }* }

(b) { x1#x2#...#xk | k ¿ 1, each xi ¿ { 0,1 }*, and for some i ¿ j, xi = xjR }
from doc - Problem 1

But i cannot understand what is expected from us to do? What does # means and what do questions mean ? Can you explain(not solving) any of the questions?

GwynforWeb

The # is another character from the alphabet acting as a separator. The R superscript is the string reversed.

(a) So an example string in the first language is 0000#1111 {alphabet = (0,1,#)}

(b) For problem 1 on the sheet, Take X in {0,1}*, eg

X = 10110010

W= 1100 is a substring of X

W^R ( ie W reversed) is 0011

so 0011#X = 0011#10110010

is in the language. {The languages alphabet is = (0,1,#)}