LTL is a star-free language but it can describe $a^*b^omega$. Contradiction?
$begingroup$
Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following language with the star: $a^*b^omega$?
$$mathbf{G}(a implies amathbf{U}b) land G(b implies mathbf{X}b)$$
So, what does the sentence "LTL is star-free language" mean? Can you give an example of regular language with star which cannot be expressed in LTL? (not an example of LTL < NBA, but an example of LTL < regular language with star)
logic formal-languages
asked Mar 5 '12 at 13:02
AyratAyrat
20519
$endgroup$
add a comment |
$begingroup$
Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following language with the star: $a^*b^omega$?
$$mathbf{G}(a implies amathbf{U}b) land G(b implies mathbf{X}b)$$
So, what does the sentence "LTL is star-free language" mean? Can you give an example of regular language with star which cannot be expressed in LTL? (not an example of LTL < NBA, but an example of LTL < regular language with star)
logic formal-languages
asked Mar 5 '12 at 13:02
AyratAyrat
20519
$endgroup$
1
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
2
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
1
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27
add a comment |
$begingroup$
Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following language with the star: $a^*b^omega$?
$$mathbf{G}(a implies amathbf{U}b) land G(b implies mathbf{X}b)$$
So, what does the sentence "LTL is star-free language" mean? Can you give an example of regular language with star which cannot be expressed in LTL? (not an example of LTL < NBA, but an example of LTL < regular language with star)
logic formal-languages
asked Mar 5 '12 at 13:02
AyratAyrat
20519
$endgroup$
Does the statement "LTL is a star-free language"(from wiki) mean that the expressiveness power of LTL is equivalent to that of star-free languages? Then why can you describe in LTL the following language with the star: $a^*b^omega$?
$$mathbf{G}(a implies amathbf{U}b) land G(b implies mathbf{X}b)$$
So, what does the sentence "LTL is star-free language" mean? Can you give an example of regular language with star which cannot be expressed in LTL? (not an example of LTL < NBA, but an example of LTL < regular language with star)
logic formal-languages
logic formal-languages
asked Mar 5 '12 at 13:02
AyratAyrat
20519
asked Mar 5 '12 at 13:02
AyratAyrat
20519
edited Dec 4 '18 at 5:35
Ayrat
asked Mar 5 '12 at 13:02
AyratAyrat
20519
asked Mar 5 '12 at 13:02
AyratAyrat
20519
asked Mar 5 '12 at 13:02
AyratAyrat
20519
20519
1
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
2
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
1
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27
add a comment |
1
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
2
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
1
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27
1
1
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
2
2
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
1
1
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Short answer: $a^*b^{omega}$ describes a star-free language.
Longer answer:
In order to show that let's consider two definitions of a regular star-free language :
- Language has a maximum star height of 0.
- Language is in the class of star-free languages, which is defined as follows:
it's the smallest subset of $Sigma^{omega}$ which contains $Sigma^{omega}$, all singletons ${x}$, $x in Sigma$, and which is closed under finite union, concatenation and complementation.
It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.
An $omega$-regular language is called $omega$-star-free if it's a finite union of languages of type $XY^{omega}$, where $X$ and $Y^+$ are star-free.
Now, $L = a^*$ can be described as $Sigma^* setminus (Sigma^* (Sigma setminus a) Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{omega}$ can be written as concatenation in the form of $XY^{omega}$ where $X = L$ and $Y = {b}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.
For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words
edited Apr 19 '12 at 14:13
Ayrat
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
$endgroup$
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
add a comment |
$begingroup$
Indeed, the language $a^*b^omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where
$$L_1=Sigma^*bbackslash(Sigma^*(Sigmabackslash a)Sigma^*b)$$
and
$$L_2=Sigma^omegabackslash(Sigma^*(Sigmabackslash b)Sigma^omega).$$
In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^omega$.
Note that for star-free expressions, Kleen-closure ($*$ and $omega$) can only be applied to $Sigma$ (the whole alphabet set).
B.T.W., you may simplify your LTL expression, and you can just use $a{bf U}({bf G}b)$.
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
$endgroup$
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
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',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f116671%2fltl-is-a-star-free-language-but-it-can-describe-ab-omega-contradiction%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Short answer: $a^*b^{omega}$ describes a star-free language.
Longer answer:
In order to show that let's consider two definitions of a regular star-free language :
- Language has a maximum star height of 0.
- Language is in the class of star-free languages, which is defined as follows:
it's the smallest subset of $Sigma^{omega}$ which contains $Sigma^{omega}$, all singletons ${x}$, $x in Sigma$, and which is closed under finite union, concatenation and complementation.
It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.
An $omega$-regular language is called $omega$-star-free if it's a finite union of languages of type $XY^{omega}$, where $X$ and $Y^+$ are star-free.
Now, $L = a^*$ can be described as $Sigma^* setminus (Sigma^* (Sigma setminus a) Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{omega}$ can be written as concatenation in the form of $XY^{omega}$ where $X = L$ and $Y = {b}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.
For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words
edited Apr 19 '12 at 14:13
Ayrat
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
$endgroup$
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
add a comment |
$begingroup$
Short answer: $a^*b^{omega}$ describes a star-free language.
Longer answer:
In order to show that let's consider two definitions of a regular star-free language :
- Language has a maximum star height of 0.
- Language is in the class of star-free languages, which is defined as follows:
it's the smallest subset of $Sigma^{omega}$ which contains $Sigma^{omega}$, all singletons ${x}$, $x in Sigma$, and which is closed under finite union, concatenation and complementation.
It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.
An $omega$-regular language is called $omega$-star-free if it's a finite union of languages of type $XY^{omega}$, where $X$ and $Y^+$ are star-free.
Now, $L = a^*$ can be described as $Sigma^* setminus (Sigma^* (Sigma setminus a) Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{omega}$ can be written as concatenation in the form of $XY^{omega}$ where $X = L$ and $Y = {b}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.
For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words
edited Apr 19 '12 at 14:13
Ayrat
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
$endgroup$
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
add a comment |
$begingroup$
Short answer: $a^*b^{omega}$ describes a star-free language.
Longer answer:
In order to show that let's consider two definitions of a regular star-free language :
- Language has a maximum star height of 0.
- Language is in the class of star-free languages, which is defined as follows:
it's the smallest subset of $Sigma^{omega}$ which contains $Sigma^{omega}$, all singletons ${x}$, $x in Sigma$, and which is closed under finite union, concatenation and complementation.
It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.
An $omega$-regular language is called $omega$-star-free if it's a finite union of languages of type $XY^{omega}$, where $X$ and $Y^+$ are star-free.
Now, $L = a^*$ can be described as $Sigma^* setminus (Sigma^* (Sigma setminus a) Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{omega}$ can be written as concatenation in the form of $XY^{omega}$ where $X = L$ and $Y = {b}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.
For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words
edited Apr 19 '12 at 14:13
Ayrat
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
$endgroup$
Short answer: $a^*b^{omega}$ describes a star-free language.
Longer answer:
In order to show that let's consider two definitions of a regular star-free language :
- Language has a maximum star height of 0.
- Language is in the class of star-free languages, which is defined as follows:
it's the smallest subset of $Sigma^{omega}$ which contains $Sigma^{omega}$, all singletons ${x}$, $x in Sigma$, and which is closed under finite union, concatenation and complementation.
It's possible to see that those two definitions are equivalent. We can also note that all finite languages are star-free.
An $omega$-regular language is called $omega$-star-free if it's a finite union of languages of type $XY^{omega}$, where $X$ and $Y^+$ are star-free.
Now, $L = a^*$ can be described as $Sigma^* setminus (Sigma^* (Sigma setminus a) Sigma^*)$, so $L$ is a star-free language. Since $L' = a^* b^{omega}$ can be written as concatenation in the form of $XY^{omega}$ where $X = L$ and $Y = {b}$ (it's easy to show that $Y^+$ is star-free) we can conclude that $L'$ is star-free.
For more information (and equivalent definitions) I can refer you to the following papers: First-order definable languages, On the Expressive Power of Temporal Logic, On the expressive power of temporal logic for infinite words
edited Apr 19 '12 at 14:13
Ayrat
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
edited Apr 19 '12 at 14:13
Ayrat
20519
edited Apr 19 '12 at 14:13
Ayrat
20519
edited Apr 19 '12 at 14:13
Ayrat
20519
20519
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
answered Apr 8 '12 at 10:31
DaniilDaniil
5462621
5462621
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
add a comment |
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
$begingroup$
Quite complicated(didn't actually get details), I think this is easier(and likely the same): omega-star free language is the lang that can be represented as $XY^omega$, where $X$, $Y$ are star-free regular languages(can be expressed with $neg$, $cup$, $emptyset$, {single letter of $Sigma$}). Since $a^* = neg(Sigma^*bSigma^*)$, where $Sigma^*=negemptyset$, is star-free regular, and single letter $b$ is also star-free regular => $a^*b^{omega}$ is $omega$-star-free regular. Thanks for refs and inspiring.
$endgroup$
– Ayrat
Apr 15 '12 at 20:10
add a comment |
$begingroup$
Indeed, the language $a^*b^omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where
$$L_1=Sigma^*bbackslash(Sigma^*(Sigmabackslash a)Sigma^*b)$$
and
$$L_2=Sigma^omegabackslash(Sigma^*(Sigmabackslash b)Sigma^omega).$$
In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^omega$.
Note that for star-free expressions, Kleen-closure ($*$ and $omega$) can only be applied to $Sigma$ (the whole alphabet set).
B.T.W., you may simplify your LTL expression, and you can just use $a{bf U}({bf G}b)$.
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
$endgroup$
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
add a comment |
$begingroup$
Indeed, the language $a^*b^omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where
$$L_1=Sigma^*bbackslash(Sigma^*(Sigmabackslash a)Sigma^*b)$$
and
$$L_2=Sigma^omegabackslash(Sigma^*(Sigmabackslash b)Sigma^omega).$$
In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^omega$.
Note that for star-free expressions, Kleen-closure ($*$ and $omega$) can only be applied to $Sigma$ (the whole alphabet set).
B.T.W., you may simplify your LTL expression, and you can just use $a{bf U}({bf G}b)$.
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
$endgroup$
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
add a comment |
$begingroup$
Indeed, the language $a^*b^omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where
$$L_1=Sigma^*bbackslash(Sigma^*(Sigmabackslash a)Sigma^*b)$$
and
$$L_2=Sigma^omegabackslash(Sigma^*(Sigmabackslash b)Sigma^omega).$$
In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^omega$.
Note that for star-free expressions, Kleen-closure ($*$ and $omega$) can only be applied to $Sigma$ (the whole alphabet set).
B.T.W., you may simplify your LTL expression, and you can just use $a{bf U}({bf G}b)$.
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
$endgroup$
Indeed, the language $a^*b^omega$ is star-free, and it can be equivalently captured by $L_1L_2$, where
$$L_1=Sigma^*bbackslash(Sigma^*(Sigmabackslash a)Sigma^*b)$$
and
$$L_2=Sigma^omegabackslash(Sigma^*(Sigmabackslash b)Sigma^omega).$$
In the above, $L_1$ and $L_2$ are respectively equal to $a^*b$ and $b^omega$.
Note that for star-free expressions, Kleen-closure ($*$ and $omega$) can only be applied to $Sigma$ (the whole alphabet set).
B.T.W., you may simplify your LTL expression, and you can just use $a{bf U}({bf G}b)$.
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
edited Apr 17 '12 at 15:24
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
answered Apr 17 '12 at 15:09
Wanwei LiuWanwei Liu
313
313
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
add a comment |
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
$begingroup$
why do you need $L1$ to represent $a^*b$ and not just $a^*$ as in the previous answer? seems to be no difference. Thanks for the note and $L2$!
$endgroup$
– Ayrat
Apr 19 '12 at 13:50
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f116671%2fltl-is-a-star-free-language-but-it-can-describe-ab-omega-contradiction%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
1
$begingroup$
Star-free languages allow all Boolean operators, including concatenation; that makes it possible to describe some languages that are more naturally described using the star.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 13:29
$begingroup$
@BrianM.Scott sorry, didn't get your point: LTL also allows Boolean operators including concatenation and complementation..
$endgroup$
– Ayrat
Mar 5 '12 at 13:52
2
$begingroup$
The point is that although you’ve used the star to describe $a^*b^omega$, that doesn’t mean that this language is not star-free. You should try to find a different description of it that doesn’t use the star; I’ve not checked carefully, but I suspect that you can use the same idea that’s used in the example in the Wikipedia article to which I linked.
$endgroup$
– Brian M. Scott
Mar 5 '12 at 14:04
1
$begingroup$
I have found this expository paper that might be of interest. It appears that $(aa)^*$ is not a star-free language.
$endgroup$
– user642796
Mar 5 '12 at 15:36
$begingroup$
You misquote Wikipedia. The phrase you use would suggest that the language of LTL formula was star-free, which does not match your question at all.
$endgroup$
– Raphael
Apr 11 '12 at 10:27