Mixing
Are context free languages closed under taking substring?
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let $L$ be context free and $Sigma $ an alphabet
Define $s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L$
Is $s(L)$ context free ?
I haven't been able to find a counterexample so im thinking i have to prove it.
I was trying to use the closure properties. $s(L)$ obviously contains $L$ so maybe i can write $s(L)$ as the union of several context free languages.
Could i please get some help, im stuck.
discrete-mathematics logic computer-science formal-languages context-free-grammar
edited Jul 30 at 22:55
Michael Hardy
204k23185460
asked Jul 30 at 20:17
asddf
746518
add a comment |Â
up vote
1
down vote
favorite
Let $L$ be context free and $Sigma $ an alphabet
Define $s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L$
Is $s(L)$ context free ?
I haven't been able to find a counterexample so im thinking i have to prove it.
I was trying to use the closure properties. $s(L)$ obviously contains $L$ so maybe i can write $s(L)$ as the union of several context free languages.
Could i please get some help, im stuck.
discrete-mathematics logic computer-science formal-languages context-free-grammar
edited Jul 30 at 22:55
Michael Hardy
204k23185460
asked Jul 30 at 20:17
asddf
746518
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let $L$ be context free and $Sigma $ an alphabet
Define $s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L$
Is $s(L)$ context free ?
I haven't been able to find a counterexample so im thinking i have to prove it.
I was trying to use the closure properties. $s(L)$ obviously contains $L$ so maybe i can write $s(L)$ as the union of several context free languages.
Could i please get some help, im stuck.
discrete-mathematics logic computer-science formal-languages context-free-grammar
edited Jul 30 at 22:55
Michael Hardy
204k23185460
asked Jul 30 at 20:17
asddf
746518
Let $L$ be context free and $Sigma $ an alphabet
Define $s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L$
Is $s(L)$ context free ?
I haven't been able to find a counterexample so im thinking i have to prove it.
I was trying to use the closure properties. $s(L)$ obviously contains $L$ so maybe i can write $s(L)$ as the union of several context free languages.
Could i please get some help, im stuck.
discrete-mathematics logic computer-science formal-languages context-free-grammar
edited Jul 30 at 22:55
Michael Hardy
204k23185460
asked Jul 30 at 20:17
asddf
746518
edited Jul 30 at 22:55
Michael Hardy
204k23185460
edited Jul 30 at 22:55
Michael Hardy
204k23185460
edited Jul 30 at 22:55
Michael Hardy
204k23185460
204k23185460
asked Jul 30 at 20:17
asddf
746518
asked Jul 30 at 20:17
asddf
746518
asked Jul 30 at 20:17
asddf
746518
746518
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57
add a comment |Â
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
Maybe a PDA is easier or more intuitive than the grammar. Suppose you have a PDA $A$ for $L$. You can then build a new one for s(L) in the following manner:
From the start you run $A$, but not on the input. Rather it guesses nondeterministically some letter that it could have read and acts if as $A§ had read it.
At some point you guess that the substring starts. Now the head actually starts moving and reads the input just as $A$ would do - however, in contracts to just $A$ the stack is not empty at the beginning.
When all the input is read, you start another "virtual" phase for $A$, reading guessed letters. If you arrive at an accepting configuration, you accept.
The new automaton has an accepting run for every substring of a word from $L$.
answered Jul 31 at 9:21
Peter Leupold
4506
add a comment |Â
up vote
0
down vote
Hint: given a CFG grammar $G$ for $L$, construct a grammar $G'$ that generates all possible substrings.
This involves adding a lot of rules that start in the middle of an original rule, followed by adding a lot of possible suffixes for each rule. It is a bit tricky to get correct, but definitely possible.
answered Jul 30 at 22:56
orlp
6,5951228
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Maybe a PDA is easier or more intuitive than the grammar. Suppose you have a PDA $A$ for $L$. You can then build a new one for s(L) in the following manner:
From the start you run $A$, but not on the input. Rather it guesses nondeterministically some letter that it could have read and acts if as $A§ had read it.
At some point you guess that the substring starts. Now the head actually starts moving and reads the input just as $A$ would do - however, in contracts to just $A$ the stack is not empty at the beginning.
When all the input is read, you start another "virtual" phase for $A$, reading guessed letters. If you arrive at an accepting configuration, you accept.
The new automaton has an accepting run for every substring of a word from $L$.
answered Jul 31 at 9:21
Peter Leupold
4506
add a comment |Â
up vote
1
down vote
Maybe a PDA is easier or more intuitive than the grammar. Suppose you have a PDA $A$ for $L$. You can then build a new one for s(L) in the following manner:
From the start you run $A$, but not on the input. Rather it guesses nondeterministically some letter that it could have read and acts if as $A§ had read it.
At some point you guess that the substring starts. Now the head actually starts moving and reads the input just as $A$ would do - however, in contracts to just $A$ the stack is not empty at the beginning.
When all the input is read, you start another "virtual" phase for $A$, reading guessed letters. If you arrive at an accepting configuration, you accept.
The new automaton has an accepting run for every substring of a word from $L$.
answered Jul 31 at 9:21
Peter Leupold
4506
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Maybe a PDA is easier or more intuitive than the grammar. Suppose you have a PDA $A$ for $L$. You can then build a new one for s(L) in the following manner:
From the start you run $A$, but not on the input. Rather it guesses nondeterministically some letter that it could have read and acts if as $A§ had read it.
At some point you guess that the substring starts. Now the head actually starts moving and reads the input just as $A$ would do - however, in contracts to just $A$ the stack is not empty at the beginning.
When all the input is read, you start another "virtual" phase for $A$, reading guessed letters. If you arrive at an accepting configuration, you accept.
The new automaton has an accepting run for every substring of a word from $L$.
answered Jul 31 at 9:21
Peter Leupold
4506
Maybe a PDA is easier or more intuitive than the grammar. Suppose you have a PDA $A$ for $L$. You can then build a new one for s(L) in the following manner:
From the start you run $A$, but not on the input. Rather it guesses nondeterministically some letter that it could have read and acts if as $A§ had read it.
At some point you guess that the substring starts. Now the head actually starts moving and reads the input just as $A$ would do - however, in contracts to just $A$ the stack is not empty at the beginning.
When all the input is read, you start another "virtual" phase for $A$, reading guessed letters. If you arrive at an accepting configuration, you accept.
The new automaton has an accepting run for every substring of a word from $L$.
answered Jul 31 at 9:21
Peter Leupold
4506
answered Jul 31 at 9:21
Peter Leupold
4506
answered Jul 31 at 9:21
Peter Leupold
4506
answered Jul 31 at 9:21
Peter Leupold
4506
4506
add a comment |Â
add a comment |Â
up vote
0
down vote
Hint: given a CFG grammar $G$ for $L$, construct a grammar $G'$ that generates all possible substrings.
This involves adding a lot of rules that start in the middle of an original rule, followed by adding a lot of possible suffixes for each rule. It is a bit tricky to get correct, but definitely possible.
answered Jul 30 at 22:56
orlp
6,5951228
add a comment |Â
up vote
0
down vote
Hint: given a CFG grammar $G$ for $L$, construct a grammar $G'$ that generates all possible substrings.
This involves adding a lot of rules that start in the middle of an original rule, followed by adding a lot of possible suffixes for each rule. It is a bit tricky to get correct, but definitely possible.
answered Jul 30 at 22:56
orlp
6,5951228
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Hint: given a CFG grammar $G$ for $L$, construct a grammar $G'$ that generates all possible substrings.
This involves adding a lot of rules that start in the middle of an original rule, followed by adding a lot of possible suffixes for each rule. It is a bit tricky to get correct, but definitely possible.
answered Jul 30 at 22:56
orlp
6,5951228
Hint: given a CFG grammar $G$ for $L$, construct a grammar $G'$ that generates all possible substrings.
This involves adding a lot of rules that start in the middle of an original rule, followed by adding a lot of possible suffixes for each rule. It is a bit tricky to get correct, but definitely possible.
answered Jul 30 at 22:56
orlp
6,5951228
answered Jul 30 at 22:56
orlp
6,5951228
answered Jul 30 at 22:56
orlp
6,5951228
answered Jul 30 at 22:56
orlp
6,5951228
6,5951228
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867376%2fare-context-free-languages-closed-under-taking-substring%23new-answer', 'question_page');
);
Post as a guest
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
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
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
See my edit to the question for proper MathJax usage. In particular, in $$ s(L):=y in Sigma ^*mid exists x,z in Sigma ^*: xyz in L, $$ the $textcurly braces$ should not be excluded from MathJax. Also not the use of mid.
– Michael Hardy
Jul 30 at 22:57