CFG for $L=biga^ib^jc^kmid kneq i+jtext and i,j,k ge0big$

up vote
1
down vote

favorite

For general, I don't know how to check that my solution is right for all cases.
For instance, the string $bb in L$ but I don't know how to create it, so I need help solving it.

Thanks.

edited Aug 2 at 17:37

asked Aug 2 at 17:14

Asaf

828

What do you mean by "check"? Do you mean to verify that the grammar derives some example elements of the language or to prove that the grammar generates the language?
â€“Â Myath
Aug 2 at 17:28

For general, I don't know how to prove that the grammar generates the language. In my case, I need help to solve the question and to understand how do I prove it.
â€“Â Asaf
Aug 2 at 17:47

add a commentÂ |Â

up vote
1
down vote

favorite

For general, I don't know how to check that my solution is right for all cases.
For instance, the string $bb in L$ but I don't know how to create it, so I need help solving it.

Thanks.

edited Aug 2 at 17:37

asked Aug 2 at 17:14

Asaf

828

What do you mean by "check"? Do you mean to verify that the grammar derives some example elements of the language or to prove that the grammar generates the language?
â€“Â Myath
Aug 2 at 17:28

For general, I don't know how to prove that the grammar generates the language. In my case, I need help to solve the question and to understand how do I prove it.
â€“Â Asaf
Aug 2 at 17:47

add a commentÂ |Â

up vote
1
down vote

favorite

For general, I don't know how to check that my solution is right for all cases.
For instance, the string $bb in L$ but I don't know how to create it, so I need help solving it.

Thanks.

edited Aug 2 at 17:37

asked Aug 2 at 17:14

Asaf

828

For general, I don't know how to check that my solution is right for all cases.
For instance, the string $bb in L$ but I don't know how to create it, so I need help solving it.

Thanks.

edited Aug 2 at 17:37

asked Aug 2 at 17:14

Asaf

828

edited Aug 2 at 17:37

asked Aug 2 at 17:14

Asaf

828

asked Aug 2 at 17:14

Asaf

828

asked Aug 2 at 17:14

Asaf

828

What do you mean by "check"? Do you mean to verify that the grammar derives some example elements of the language or to prove that the grammar generates the language?
â€“Â Myath
Aug 2 at 17:28

For general, I don't know how to prove that the grammar generates the language. In my case, I need help to solve the question and to understand how do I prove it.
â€“Â Asaf
Aug 2 at 17:47

add a commentÂ |Â

What do you mean by "check"? Do you mean to verify that the grammar derives some example elements of the language or to prove that the grammar generates the language?
â€“Â Myath
Aug 2 at 17:28

For general, I don't know how to prove that the grammar generates the language. In my case, I need help to solve the question and to understand how do I prove it.
â€“Â Asaf
Aug 2 at 17:47

What do you mean by "check"? Do you mean to verify that the grammar derives some example elements of the language or to prove that the grammar generates the language?
â€“Â Myath
Aug 2 at 17:28

For general, I don't know how to prove that the grammar generates the language. In my case, I need help to solve the question and to understand how do I prove it.
â€“Â Asaf
Aug 2 at 17:47

add a commentÂ |Â

1 Answer
1

active

oldest

votes

up vote
2
down vote

accepted

The part of the grammar for $S_4$ that is supposed to generate the second subset of the language is wrong because $S_4$ always derives a string that starts with $a$.
You can split it up into cases: one starts with $a$ and the other starts with $b$.

I think the easiest way to prove this is by what's called structural induction.
I'm going to show that $S_4$ generates the second subset of the language. Then you can try to mimic to prove that $S_1$ generates the first subset of the language.

Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)

To prove that $S_4$ generates the second subset of the language, you need to prove 2 directions: for any string $s$ in the subset, there's a derivation from $S_4$ to $s$; and any string derived by $S_4$ is in the subset.

One direction:

Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.

If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.

If $m > 0$, apply 1.1, 2.2 $x=min(k,m-1)$ times, 2.1 $max(0, m-1-x)$ times,
3.2 $y = min(k-x, n)$ times, 3.1 $max(0, n-y)$ times, then 3.3.

You can try to verify that the numbers add up.

The other direction:

This is where you use structural induction.

First show $S_6$ generates $b^nc^k mid n ge k$.

Then show that any derivation from $S_5$ has an intermediate in $a^mS_6c^k mid m ge k$.

So $bS_6$ generates $b^nc^k mid n > k$ and
$S_5$ generates $a^mb^nc^k mid m + n ge k$.

Hence, $aS_5$ generates $a^mb^nc^k mid m > 0, m + n > k$.

Conclude that $S_4$ generates $a^mb^nc^k mid m+n > k$.

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\$","\$"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2870296%2fcfg-for-l-big-aibjck-mid-k-neq-ij-text-and-i-j-k-ge0-big%23new-answer', 'question_page');

);

Post as a guest

Name

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

up vote
2
down vote

accepted

Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)

One direction:

Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.

If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.

If $m > 0$, apply 1.1, 2.2 $x=min(k,m-1)$ times, 2.1 $max(0, m-1-x)$ times,
3.2 $y = min(k-x, n)$ times, 3.1 $max(0, n-y)$ times, then 3.3.

You can try to verify that the numbers add up.

The other direction:

This is where you use structural induction.

First show $S_6$ generates $b^nc^k mid n ge k$.

Then show that any derivation from $S_5$ has an intermediate in $a^mS_6c^k mid m ge k$.

So $bS_6$ generates $b^nc^k mid n > k$ and
$S_5$ generates $a^mb^nc^k mid m + n ge k$.

Hence, $aS_5$ generates $a^mb^nc^k mid m > 0, m + n > k$.

Conclude that $S_4$ generates $a^mb^nc^k mid m+n > k$.

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

add a commentÂ |Â

up vote
2
down vote

accepted

Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)

One direction:

Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.

If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.

If $m > 0$, apply 1.1, 2.2 $x=min(k,m-1)$ times, 2.1 $max(0, m-1-x)$ times,
3.2 $y = min(k-x, n)$ times, 3.1 $max(0, n-y)$ times, then 3.3.

You can try to verify that the numbers add up.

The other direction:

This is where you use structural induction.

First show $S_6$ generates $b^nc^k mid n ge k$.

Then show that any derivation from $S_5$ has an intermediate in $a^mS_6c^k mid m ge k$.

So $bS_6$ generates $b^nc^k mid n > k$ and
$S_5$ generates $a^mb^nc^k mid m + n ge k$.

Hence, $aS_5$ generates $a^mb^nc^k mid m > 0, m + n > k$.

Conclude that $S_4$ generates $a^mb^nc^k mid m+n > k$.

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

add a commentÂ |Â

up vote
2
down vote

accepted

Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)

One direction:

Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.

If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.

If $m > 0$, apply 1.1, 2.2 $x=min(k,m-1)$ times, 2.1 $max(0, m-1-x)$ times,
3.2 $y = min(k-x, n)$ times, 3.1 $max(0, n-y)$ times, then 3.3.

You can try to verify that the numbers add up.

The other direction:

This is where you use structural induction.

First show $S_6$ generates $b^nc^k mid n ge k$.

Then show that any derivation from $S_5$ has an intermediate in $a^mS_6c^k mid m ge k$.

So $bS_6$ generates $b^nc^k mid n > k$ and
$S_5$ generates $a^mb^nc^k mid m + n ge k$.

Hence, $aS_5$ generates $a^mb^nc^k mid m > 0, m + n > k$.

Conclude that $S_4$ generates $a^mb^nc^k mid m+n > k$.

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

Let's number the rules to make this easier: 1.1, 1.2, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3. (The format is row-number.column-number)

One direction:

Let $s = a^mb^nc^k$ with $m + n > k$. Then come up with a specific derivation for $s$ from $S_4$. Split this into cases.

If $m = 0$, apply 1.2 once, 3.2 $k$ times, $3.1$ $n-k$ times, then 3.3.

If $m > 0$, apply 1.1, 2.2 $x=min(k,m-1)$ times, 2.1 $max(0, m-1-x)$ times,
3.2 $y = min(k-x, n)$ times, 3.1 $max(0, n-y)$ times, then 3.3.

You can try to verify that the numbers add up.

The other direction:

This is where you use structural induction.

First show $S_6$ generates $b^nc^k mid n ge k$.

Then show that any derivation from $S_5$ has an intermediate in $a^mS_6c^k mid m ge k$.

So $bS_6$ generates $b^nc^k mid n > k$ and
$S_5$ generates $a^mb^nc^k mid m + n ge k$.

Hence, $aS_5$ generates $a^mb^nc^k mid m > 0, m + n > k$.

Conclude that $S_4$ generates $a^mb^nc^k mid m+n > k$.

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

edited Aug 2 at 18:33

answered Aug 2 at 18:27

Myath

769414

answered Aug 2 at 18:27

Myath

769414

answered Aug 2 at 18:27

Myath

769414

add a commentÂ |Â

draft saved

draft discarded

draft saved

draft discarded

Post as a guest

Name

Search This Blog

ukmuiik