Mixing
Show that the following language is context-free/not context free by expressing the language as the union of...
up vote
1
down vote
favorite
I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$, and $L_3$.
By knowing if these three other languages are context-free/not context-free, I hope to indicate whether the language $L$ is context-free/not context-free.
Can anyone help me pick these three other languages that when unioned together form $L$?
combinatorics formal-languages regular-language context-free-grammar
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
favorite
I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$, and $L_3$.
By knowing if these three other languages are context-free/not context-free, I hope to indicate whether the language $L$ is context-free/not context-free.
Can anyone help me pick these three other languages that when unioned together form $L$?
combinatorics formal-languages regular-language context-free-grammar
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$, and $L_3$.
By knowing if these three other languages are context-free/not context-free, I hope to indicate whether the language $L$ is context-free/not context-free.
Can anyone help me pick these three other languages that when unioned together form $L$?
combinatorics formal-languages regular-language context-free-grammar
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$, and $L_3$.
By knowing if these three other languages are context-free/not context-free, I hope to indicate whether the language $L$ is context-free/not context-free.
Can anyone help me pick these three other languages that when unioned together form $L$?
combinatorics formal-languages regular-language context-free-grammar
combinatorics formal-languages regular-language context-free-grammar
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
etnie1031
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
etnie1031
132
asked 2 days ago
etnie1031
132
132
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
etnie1031 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago
add a comment |
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
Let $L_1={a^mba^nba^p:m=n}$. Consider the following grammar that generates this language with starting symbol $S$: $$
Slongrightarrow Cbtext{ }|text{ }Sa \
C longrightarrow btext{ }|text{ }aCa
$$
This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2={a^mba^nba^p:n=p}$ is context-free.
Let $L_3={a^mba^nba^p:m=p}$. Consider the following grammar that generates this language with starting symbol $S$:
$$
Slongrightarrow bCbtext{ }|text{ }aSa \
C longrightarrow epsilontext{ }|text{ }aC
$$
This grammar is context-free, so $L_3$ is context-free. Since $L=L_1cup L_2cup L_3$, then $L$ is context-free.
answered 2 days ago
Joey Kilpatrick
1,070121
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
Let $L_1={a^mba^nba^p:m=n}$. Consider the following grammar that generates this language with starting symbol $S$: $$
Slongrightarrow Cbtext{ }|text{ }Sa \
C longrightarrow btext{ }|text{ }aCa
$$
This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2={a^mba^nba^p:n=p}$ is context-free.
Let $L_3={a^mba^nba^p:m=p}$. Consider the following grammar that generates this language with starting symbol $S$:
$$
Slongrightarrow bCbtext{ }|text{ }aSa \
C longrightarrow epsilontext{ }|text{ }aC
$$
This grammar is context-free, so $L_3$ is context-free. Since $L=L_1cup L_2cup L_3$, then $L$ is context-free.
answered 2 days ago
Joey Kilpatrick
1,070121
add a comment |
up vote
0
down vote
Let $L_1={a^mba^nba^p:m=n}$. Consider the following grammar that generates this language with starting symbol $S$: $$
Slongrightarrow Cbtext{ }|text{ }Sa \
C longrightarrow btext{ }|text{ }aCa
$$
This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2={a^mba^nba^p:n=p}$ is context-free.
Let $L_3={a^mba^nba^p:m=p}$. Consider the following grammar that generates this language with starting symbol $S$:
$$
Slongrightarrow bCbtext{ }|text{ }aSa \
C longrightarrow epsilontext{ }|text{ }aC
$$
This grammar is context-free, so $L_3$ is context-free. Since $L=L_1cup L_2cup L_3$, then $L$ is context-free.
answered 2 days ago
Joey Kilpatrick
1,070121
add a comment |
up vote
0
down vote
up vote
0
down vote
Let $L_1={a^mba^nba^p:m=n}$. Consider the following grammar that generates this language with starting symbol $S$: $$
Slongrightarrow Cbtext{ }|text{ }Sa \
C longrightarrow btext{ }|text{ }aCa
$$
This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2={a^mba^nba^p:n=p}$ is context-free.
Let $L_3={a^mba^nba^p:m=p}$. Consider the following grammar that generates this language with starting symbol $S$:
$$
Slongrightarrow bCbtext{ }|text{ }aSa \
C longrightarrow epsilontext{ }|text{ }aC
$$
This grammar is context-free, so $L_3$ is context-free. Since $L=L_1cup L_2cup L_3$, then $L$ is context-free.
answered 2 days ago
Joey Kilpatrick
1,070121
Let $L_1={a^mba^nba^p:m=n}$. Consider the following grammar that generates this language with starting symbol $S$: $$
Slongrightarrow Cbtext{ }|text{ }Sa \
C longrightarrow btext{ }|text{ }aCa
$$
This grammar is context-free, so $L_1$ is context-free. A similar grammar will show that $L_2={a^mba^nba^p:n=p}$ is context-free.
Let $L_3={a^mba^nba^p:m=p}$. Consider the following grammar that generates this language with starting symbol $S$:
$$
Slongrightarrow bCbtext{ }|text{ }aSa \
C longrightarrow epsilontext{ }|text{ }aC
$$
This grammar is context-free, so $L_3$ is context-free. Since $L=L_1cup L_2cup L_3$, then $L$ is context-free.
answered 2 days ago
Joey Kilpatrick
1,070121
answered 2 days ago
Joey Kilpatrick
1,070121
answered 2 days ago
Joey Kilpatrick
1,070121
answered 2 days ago
Joey Kilpatrick
1,070121
1,070121
add a comment |
add a comment |
etnie1031 is a new contributor. Be nice, and check out our Code of Conduct.
etnie1031 is a new contributor. Be nice, and check out our Code of Conduct.
etnie1031 is a new contributor. Be nice, and check out our Code of Conduct.
etnie1031 is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3005281%2fshow-that-the-following-language-is-context-free-not-context-free-by-expressing%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
Doesn't the use of "or" in the language description to join three possible conditions give you a clue?
– rici
2 days ago