Is a particular string regular (e.g is '010') regular?Why is every finite language A ⊆ Σ* regularNull...
How to draw these kind of adjacent ovals with arrows in latex?
For US ESTA, should I mention a visa denial from before I got UK citizenship?
Is there a technology capable of disabling the whole of Earth's satellitle network?
The totem pole can be grouped into
Rigorous Geometric Proof That dA=rdrdθ?
Is 'bad luck' with former employees a red flag?
Can you make a Spell Glyph of a spell that has the potential to target more than one creature?
Taking an academic pseudonym?
Unable to login to ec2 instance after running “sudo chmod 2770 /”
Is it appropriate to give a culturally-traditional gift to a female coworker?
Which was the first story to feature space elevators?
Why does finding small effects in large studies indicate publication bias?
Bitcoin automatically diverted to bech32 address
Pictures from Mars
Negotiating 1-year delay to my Assistant Professor Offer
If an area is covered in both Ball Bearings and Caltrops, does the creature need to move at half speed or quarter speed to avoid both their effects?
Should corporate security training be tailored based on a users' job role?
Substitute ./ and ../ directories by actual names
Tikz - highlight text in an image
Why do climate experts from the UN/IPCC rarely mention Grand Solar Minimum?
Is candidate anonymity at all practical?
How to play song that contains one guitar when we have two guitarists (or more)?
Manager has noticed coworker's excessive breaks. Should I warn him?
Should a support incident be opened for every stack dump, or just ones that cause an outage?
Is a particular string regular (e.g is '010') regular?
Why is every finite language A ⊆ Σ* regularNull Characters and Splitting the String in the Pumping LemmaPumping lemma for simple finite regular languagesProofs using the regular pumping lemmaHow come {ww} isn't regular when {uv | |u|=|v|} is?Pumping lemma with two r languagesCan ${a^mb^nc^nmid m,n ge 1}$ be proved non-regular using the pumping lemma?Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final statesHow does a regular language satisfies the second condition of the pumping lemmaDoes a DFA on {0,1} accept any string whose length is composite/prime?Minimum pumping length of regular language
$begingroup$
if alphabet is {0,1}, then is string '010' regular?
I think it is regular because DFA and Regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.
For pumping lemma first we have to take w only in the language [here language is just '010] So w='010' I choose k = 2 then new string is w=x(y^k)z has length more than 3 so it is definitely not '010' which means this language is not Regular!
What am I missing?
formal-languages regular-languages finite-automata
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
if alphabet is {0,1}, then is string '010' regular?
I think it is regular because DFA and Regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.
For pumping lemma first we have to take w only in the language [here language is just '010] So w='010' I choose k = 2 then new string is w=x(y^k)z has length more than 3 so it is definitely not '010' which means this language is not Regular!
What am I missing?
formal-languages regular-languages finite-automata
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago
add a comment |
$begingroup$
if alphabet is {0,1}, then is string '010' regular?
I think it is regular because DFA and Regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.
For pumping lemma first we have to take w only in the language [here language is just '010] So w='010' I choose k = 2 then new string is w=x(y^k)z has length more than 3 so it is definitely not '010' which means this language is not Regular!
What am I missing?
formal-languages regular-languages finite-automata
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
if alphabet is {0,1}, then is string '010' regular?
I think it is regular because DFA and Regular languages are equivalent and this string has a DFA but at the same time it seems to contradict pumping lemma which implies not regular. Here is what I mean.
For pumping lemma first we have to take w only in the language [here language is just '010] So w='010' I choose k = 2 then new string is w=x(y^k)z has length more than 3 so it is definitely not '010' which means this language is not Regular!
What am I missing?
formal-languages regular-languages finite-automata
formal-languages regular-languages finite-automata
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 6 hours ago
Anirudh Anirudh
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 6 hours ago
Anirudh Anirudh
61
asked 6 hours ago
Anirudh Anirudh
61
61
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Anirudh is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago
add a comment |
1
$begingroup$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago
1
1
$begingroup$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago
$begingroup$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, ${ 010 }$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a regular language then there exists a constant $n$ such that for all words $w in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| leq n$ and $y neq epsilon$, such that $xy^iz in L$ for all $i geq 0$.
Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
$endgroup$
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: "419"
};
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Anirudh 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%2fcs.stackexchange.com%2fquestions%2f104557%2fis-a-particular-string-regular-e-g-is-010-regular%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, ${ 010 }$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a regular language then there exists a constant $n$ such that for all words $w in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| leq n$ and $y neq epsilon$, such that $xy^iz in L$ for all $i geq 0$.
Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
$endgroup$
add a comment |
$begingroup$
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, ${ 010 }$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a regular language then there exists a constant $n$ such that for all words $w in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| leq n$ and $y neq epsilon$, such that $xy^iz in L$ for all $i geq 0$.
Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
$endgroup$
add a comment |
$begingroup$
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, ${ 010 }$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a regular language then there exists a constant $n$ such that for all words $w in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| leq n$ and $y neq epsilon$, such that $xy^iz in L$ for all $i geq 0$.
Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
$endgroup$
Being regular is a property of languages, not of words.
However, it seems that by '010' you really mean the language consisting only of the single word '010', that is, ${ 010 }$. This language, just like any other finite language, is regular.
Where does your pumping lemma proof fail, then? Here is a complete statement of the pumping lemma.
If $L$ is a regular language then there exists a constant $n$ such that for all words $w in L$ of length at least $n$ there is a decomposition $w = xyz$, where $|xy| leq n$ and $y neq epsilon$, such that $xy^iz in L$ for all $i geq 0$.
Your argument is ignoring the constant $n$, which could be larger than the length of all words in $L$.
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
answered 6 hours ago
Yuval FilmusYuval Filmus
192k14180343
192k14180343
add a comment |
add a comment |
Anirudh is a new contributor. Be nice, and check out our Code of Conduct.
Anirudh is a new contributor. Be nice, and check out our Code of Conduct.
Anirudh is a new contributor. Be nice, and check out our Code of Conduct.
Anirudh is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Computer Science 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%2fcs.stackexchange.com%2fquestions%2f104557%2fis-a-particular-string-regular-e-g-is-010-regular%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$
Possible duplicate of Why is every finite language A ⊆ Σ* regular
$endgroup$
– dkaeae
6 hours ago