Return to Question

added 4 characters in body; edited title

Source Link

edited Oct 18, 2022 at 10:02

Morphlng

Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$

Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = {0^i1^ic0^j1^j | j = i+1}$$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

What I've tried

The difficulty is around the j = i + 1 controlling, I've tried something like this:

S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

Although it can generate all strings that L can generate, but if you take B -> c to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)

Context free grammar for $L={0^i1^ic0^j1^j | j = i+1}$

Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = {0^i1^ic0^j1^j | j = i+1}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

What I've tried

The difficulty is around the j = i + 1 controlling, I've tried something like this:

S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

Although it can generate all strings that L can generate, but if you take B -> c to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)

Context free grammar for $L= \{0^i1^ic0^j1^j | j = i+1 \}$

Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = \{ 0^i1^ic0^j1^j | j = i+1 \}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

What I've tried

The difficulty is around the j = i + 1 controlling, I've tried something like this:

S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

Although it can generate all strings that L can generate, but if you take B -> c to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)

Source Link

asked Oct 18, 2022 at 2:35

Morphlng

Context free grammar for $L={0^i1^ic0^j1^j | j = i+1}$

Description

This is an exercise for Formal Language course, I'm asked to find a grammar for language:

$L = {0^i1^ic0^j1^j | j = i+1}$

As an example: 01c0011 can be generated using this language, so does 0011c000111.

What I've tried

The difficulty is around the j = i + 1 controlling, I've tried something like this:

S -> 0A11
A -> 0A1 | 1B00
B -> 1B0 | c

Although it can generate all strings that L can generate, but if you take B -> c to terminate the generation early, the string such as "001c00111" doesn't belong to L anymore.

Can somebody give me some advice on this? Better yet, can you tell me what is the correct way to solve such problems? (given language, find CFG)