$L_4 = {x: #_{1}(x) = 2 cdot #_{10}(x) }$ Find CFG given hints
up vote
2
down vote
favorite
Attempt:
$S to A_{00}SA_{11}$
$A_{00} to 0, 0A_{00}, 0A_{10}$
$A_{01} to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$
$A_{10} to 1A_{10}, A_{10}0, 1A_{00}$
$A_{11} to 1, 1A_{11}, 1A_{01}$
Not sure what I'm doing. Any help is appreciated
context-free-grammar
add a comment |
up vote
2
down vote
favorite
Attempt:
$S to A_{00}SA_{11}$
$A_{00} to 0, 0A_{00}, 0A_{10}$
$A_{01} to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$
$A_{10} to 1A_{10}, A_{10}0, 1A_{00}$
$A_{11} to 1, 1A_{11}, 1A_{01}$
Not sure what I'm doing. Any help is appreciated
context-free-grammar
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Attempt:
$S to A_{00}SA_{11}$
$A_{00} to 0, 0A_{00}, 0A_{10}$
$A_{01} to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$
$A_{10} to 1A_{10}, A_{10}0, 1A_{00}$
$A_{11} to 1, 1A_{11}, 1A_{01}$
Not sure what I'm doing. Any help is appreciated
context-free-grammar
Attempt:
$S to A_{00}SA_{11}$
$A_{00} to 0, 0A_{00}, 0A_{10}$
$A_{01} to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$
$A_{10} to 1A_{10}, A_{10}0, 1A_{00}$
$A_{11} to 1, 1A_{11}, 1A_{01}$
Not sure what I'm doing. Any help is appreciated
context-free-grammar
context-free-grammar
asked Nov 12 at 6:48
Tree Garen
33419
33419
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
accepted
It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.
For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$.
$$
A_{00}longrightarrow 0, text{ } 0A_{00}, text{ } 0A_{10}
$$
For $A_{01}$, the same logic applies based off of the second character.
$$
A_{01}longrightarrow 0A_{01}, text{ } 0A_{11}
$$
It is more complicated for $A_{10}$ and $A_{11}$.
For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.
A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$.
$$
A_{10}longrightarrow A_{10}0, text{ } 11A_{00}, text{ } 11A_{11}0, text{ }A_{11}A_{10}
$$
For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$.
$$
A_{11}longrightarrow 1A_{00}1, text{ } 1A_{01}1, text{ } A_{10}A_{11}
$$
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.
For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$.
$$
A_{00}longrightarrow 0, text{ } 0A_{00}, text{ } 0A_{10}
$$
For $A_{01}$, the same logic applies based off of the second character.
$$
A_{01}longrightarrow 0A_{01}, text{ } 0A_{11}
$$
It is more complicated for $A_{10}$ and $A_{11}$.
For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.
A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$.
$$
A_{10}longrightarrow A_{10}0, text{ } 11A_{00}, text{ } 11A_{11}0, text{ }A_{11}A_{10}
$$
For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$.
$$
A_{11}longrightarrow 1A_{00}1, text{ } 1A_{01}1, text{ } A_{10}A_{11}
$$
add a comment |
up vote
0
down vote
accepted
It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.
For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$.
$$
A_{00}longrightarrow 0, text{ } 0A_{00}, text{ } 0A_{10}
$$
For $A_{01}$, the same logic applies based off of the second character.
$$
A_{01}longrightarrow 0A_{01}, text{ } 0A_{11}
$$
It is more complicated for $A_{10}$ and $A_{11}$.
For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.
A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$.
$$
A_{10}longrightarrow A_{10}0, text{ } 11A_{00}, text{ } 11A_{11}0, text{ }A_{11}A_{10}
$$
For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$.
$$
A_{11}longrightarrow 1A_{00}1, text{ } 1A_{01}1, text{ } A_{10}A_{11}
$$
add a comment |
up vote
0
down vote
accepted
up vote
0
down vote
accepted
It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.
For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$.
$$
A_{00}longrightarrow 0, text{ } 0A_{00}, text{ } 0A_{10}
$$
For $A_{01}$, the same logic applies based off of the second character.
$$
A_{01}longrightarrow 0A_{01}, text{ } 0A_{11}
$$
It is more complicated for $A_{10}$ and $A_{11}$.
For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.
A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$.
$$
A_{10}longrightarrow A_{10}0, text{ } 11A_{00}, text{ } 11A_{11}0, text{ }A_{11}A_{10}
$$
For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$.
$$
A_{11}longrightarrow 1A_{00}1, text{ } 1A_{01}1, text{ } A_{10}A_{11}
$$
It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.
For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$.
$$
A_{00}longrightarrow 0, text{ } 0A_{00}, text{ } 0A_{10}
$$
For $A_{01}$, the same logic applies based off of the second character.
$$
A_{01}longrightarrow 0A_{01}, text{ } 0A_{11}
$$
It is more complicated for $A_{10}$ and $A_{11}$.
For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.
A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$.
$$
A_{10}longrightarrow A_{10}0, text{ } 11A_{00}, text{ } 11A_{11}0, text{ }A_{11}A_{10}
$$
For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$.
$$
A_{11}longrightarrow 1A_{00}1, text{ } 1A_{01}1, text{ } A_{10}A_{11}
$$
answered 16 hours ago
Joey Kilpatrick
65418
65418
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2994957%2fl-4-x-1x-2-cdot-10x-find-cfg-given-hints%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown