If the string of L consists of 0's only prove that L* is regular Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara Data science time! April 2019 and salary with experience The Ask Question Wizard is Live!Regular expression to match string of 0's and 1's without '011' substringProving a Language to be regularWhat regular language intersects with 1*0* gives 1n0nUsing Closure Properties to prove RegularityProving Regular LanguagesProving that a language is regularDesign a regular expression or Finite Automata for a language that consists of 01 or 010?Prove that a context-free-grammar is regularRegular languages and pumping lemma1 or 2 right hand side variable in Context free language
How can I wire a 9-position switch so that each position turns on one more LED than the one before?
Where/What are Arya's scars from?
"Working on a knee"
Writing a T-SQL stored procedure to receive 4 numbers and insert them into a table
Why aren't road bicycle wheels tiny?
What does the black goddess statue do and what is it?
What is /etc/mtab in Linux?
Co-worker works way more than he should
Why did Europeans not widely domesticate foxes?
What do you call an IPA symbol that lacks a name (e.g. ɲ)?
How did Elite on the NES work?
Is there an efficient way for synchronising audio events real-time with LEDs using an MCU?
Why doesn't the university give past final exams' answers?
What's parked in Mil Moscow helicopter plant?
Bright yellow or light yellow?
Philosophers who were composers?
Is Bran literally the world's memory?
Why do people think Winterfell crypts is the safest place for women, children & old people?
Is it accepted to use working hours to read general interest books?
France's Public Holidays' Puzzle
TV series episode where humans nuke aliens before decrypting their message that states they come in peace
Where can I find how to tex symbols for different fonts?
Is a self contained air-bullet cartridge feasible?
All ASCII characters with a given bit count
If the string of L consists of 0's only prove that L* is regular
Unicorn Meta Zoo #1: Why another podcast?
Announcing the arrival of Valued Associate #679: Cesar Manara
Data science time! April 2019 and salary with experience
The Ask Question Wizard is Live!Regular expression to match string of 0's and 1's without '011' substringProving a Language to be regularWhat regular language intersects with 1*0* gives 1n0nUsing Closure Properties to prove RegularityProving Regular LanguagesProving that a language is regularDesign a regular expression or Finite Automata for a language that consists of 01 or 010?Prove that a context-free-grammar is regularRegular languages and pumping lemma1 or 2 right hand side variable in Context free language
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
A question 4.2.10 from Introduction to Automata Theory by Hopcroft and Ullman. The original language L can also be non-regular.
Let's say we got a function of 0^(2^n+5), n>=0, how would you prove that (0^(2^n+5))* is regular? And also for the more general case, when f(0) can be any function?
regular-language automata
asked Mar 22 at 13:42
VladimirVladimir
83
add a comment |
A question 4.2.10 from Introduction to Automata Theory by Hopcroft and Ullman. The original language L can also be non-regular.
Let's say we got a function of 0^(2^n+5), n>=0, how would you prove that (0^(2^n+5))* is regular? And also for the more general case, when f(0) can be any function?
regular-language automata
asked Mar 22 at 13:42
VladimirVladimir
83
add a comment |
A question 4.2.10 from Introduction to Automata Theory by Hopcroft and Ullman. The original language L can also be non-regular.
Let's say we got a function of 0^(2^n+5), n>=0, how would you prove that (0^(2^n+5))* is regular? And also for the more general case, when f(0) can be any function?
regular-language automata
asked Mar 22 at 13:42
VladimirVladimir
83
A question 4.2.10 from Introduction to Automata Theory by Hopcroft and Ullman. The original language L can also be non-regular.
Let's say we got a function of 0^(2^n+5), n>=0, how would you prove that (0^(2^n+5))* is regular? And also for the more general case, when f(0) can be any function?
regular-language automata
regular-language automata
asked Mar 22 at 13:42
VladimirVladimir
83
asked Mar 22 at 13:42
VladimirVladimir
83
asked Mar 22 at 13:42
VladimirVladimir
83
asked Mar 22 at 13:42
VladimirVladimir
83
asked Mar 22 at 13:42
VladimirVladimir
83
83
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Suppose that L contains two strings 0^n and 0^m and that n and m share no common factors: they are relatively prime. Then, by concatenating some number of instances of 0^n with some number of instances of 0^m, any string of length (n - 1)(m - 1) can be formed. Since L* must therefore exclude only a finite number of words, the complement (L*)' must be finite, hence regular; because regular languages are closed under complement, L* must be regular too.
Where did (n - 1)(m - 1) come from? Well, it's a special case (n = 2) of the coin problem for which we have a closed-form solution. You should be able to research this and find some proofs.
What about the case where all strings in L have lengths divisible by some GCD, say g? Well, the proof of regularity is quite similar; consider a modified alphabet where 0 is replaced by the symbol (0^g) and then prove the analogous language over this alphabet is regular as above. In other words, you can show that L* contains only strings divisible by g and all strings divisible by g of length at least (n/g - 1)(m/g - 1) where n and m have GCD g. The language is regular because it excludes only finitely many words whose lengths are divisible by g.
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
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%2fstackoverflow.com%2fquestions%2f55300950%2fif-the-string-of-l-consists-of-0s-only-prove-that-l-is-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
Suppose that L contains two strings 0^n and 0^m and that n and m share no common factors: they are relatively prime. Then, by concatenating some number of instances of 0^n with some number of instances of 0^m, any string of length (n - 1)(m - 1) can be formed. Since L* must therefore exclude only a finite number of words, the complement (L*)' must be finite, hence regular; because regular languages are closed under complement, L* must be regular too.
Where did (n - 1)(m - 1) come from? Well, it's a special case (n = 2) of the coin problem for which we have a closed-form solution. You should be able to research this and find some proofs.
What about the case where all strings in L have lengths divisible by some GCD, say g? Well, the proof of regularity is quite similar; consider a modified alphabet where 0 is replaced by the symbol (0^g) and then prove the analogous language over this alphabet is regular as above. In other words, you can show that L* contains only strings divisible by g and all strings divisible by g of length at least (n/g - 1)(m/g - 1) where n and m have GCD g. The language is regular because it excludes only finitely many words whose lengths are divisible by g.
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
add a comment |
Suppose that L contains two strings 0^n and 0^m and that n and m share no common factors: they are relatively prime. Then, by concatenating some number of instances of 0^n with some number of instances of 0^m, any string of length (n - 1)(m - 1) can be formed. Since L* must therefore exclude only a finite number of words, the complement (L*)' must be finite, hence regular; because regular languages are closed under complement, L* must be regular too.
Where did (n - 1)(m - 1) come from? Well, it's a special case (n = 2) of the coin problem for which we have a closed-form solution. You should be able to research this and find some proofs.
What about the case where all strings in L have lengths divisible by some GCD, say g? Well, the proof of regularity is quite similar; consider a modified alphabet where 0 is replaced by the symbol (0^g) and then prove the analogous language over this alphabet is regular as above. In other words, you can show that L* contains only strings divisible by g and all strings divisible by g of length at least (n/g - 1)(m/g - 1) where n and m have GCD g. The language is regular because it excludes only finitely many words whose lengths are divisible by g.
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
add a comment |
Suppose that L contains two strings 0^n and 0^m and that n and m share no common factors: they are relatively prime. Then, by concatenating some number of instances of 0^n with some number of instances of 0^m, any string of length (n - 1)(m - 1) can be formed. Since L* must therefore exclude only a finite number of words, the complement (L*)' must be finite, hence regular; because regular languages are closed under complement, L* must be regular too.
Where did (n - 1)(m - 1) come from? Well, it's a special case (n = 2) of the coin problem for which we have a closed-form solution. You should be able to research this and find some proofs.
What about the case where all strings in L have lengths divisible by some GCD, say g? Well, the proof of regularity is quite similar; consider a modified alphabet where 0 is replaced by the symbol (0^g) and then prove the analogous language over this alphabet is regular as above. In other words, you can show that L* contains only strings divisible by g and all strings divisible by g of length at least (n/g - 1)(m/g - 1) where n and m have GCD g. The language is regular because it excludes only finitely many words whose lengths are divisible by g.
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
Suppose that L contains two strings 0^n and 0^m and that n and m share no common factors: they are relatively prime. Then, by concatenating some number of instances of 0^n with some number of instances of 0^m, any string of length (n - 1)(m - 1) can be formed. Since L* must therefore exclude only a finite number of words, the complement (L*)' must be finite, hence regular; because regular languages are closed under complement, L* must be regular too.
Where did (n - 1)(m - 1) come from? Well, it's a special case (n = 2) of the coin problem for which we have a closed-form solution. You should be able to research this and find some proofs.
What about the case where all strings in L have lengths divisible by some GCD, say g? Well, the proof of regularity is quite similar; consider a modified alphabet where 0 is replaced by the symbol (0^g) and then prove the analogous language over this alphabet is regular as above. In other words, you can show that L* contains only strings divisible by g and all strings divisible by g of length at least (n/g - 1)(m/g - 1) where n and m have GCD g. The language is regular because it excludes only finitely many words whose lengths are divisible by g.
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
answered Mar 22 at 14:51
Patrick87Patrick87
18.8k32760
18.8k32760
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- 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.
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%2fstackoverflow.com%2fquestions%2f55300950%2fif-the-string-of-l-consists-of-0s-only-prove-that-l-is-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
