Bsrhrki

What favor did Moody owe Dumbledore?

What does "^L" mean in C?

Loading the leaflet Map in Lightning Web Component

Why didn't Héctor fade away after this character died in the movie Coco?

What does "Four-F." mean?

When did antialiasing start being available?

Brake pads destroying wheels

What is the significance behind "40 days" that often appears in the Bible?

Have the tides ever turned twice on any open problem?

Unfrosted light bulb

Should I use acronyms in dialogues before telling the readers what it stands for in fiction?

Is it possible to stack the damage done by the Absorb Elements spell?

Comment Box for Substitution Method of Integrals

How difficult is it to simply disable/disengage the MCAS on Boeing 737 Max 8 & 9 Aircraft?

What can I do if I am asked to learn different programming languages very frequently?

HP P840 HDD RAID 5 many strange drive failures

How to terminate ping <dest> &

Should I be concerned about student access to a test bank?

Are dual Irish/British citizens bound by the 90/180 day rule when travelling in the EU after Brexit?

A Ri-diddley-iley Riddle

PTIJ: Do Irish Jews have "the luck of the Irish"?

Generic TVP tradeoffs?

Turning a hard to access nut?

Is it true that good novels will automatically sell themselves on Amazon (and so on) and there is no need for one to waste time promoting?

Are regular expressions a*a and aa* equivalent?

How to convert finite automata to regular expressions?Finding simpler equivalent regular expressionsRegular expressions and semi-linear sets∅-free regular expressions?Why are regular expressions defined with union, concatenation and star operations?How to generate regular expression for language of regular expressions?How to read regular expressions?Regular expression for even/odd string on alphabetDo all Regular Expressions describe Regular Languages?How to prove that $$x$$ is a regular language if $x$ is derived from $L=w$ by substituting substrings?

1

1

$begingroup$

Let $Sigma = a, b$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

regular-expressions

share|cite|improve this question

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are equivalent because both accept exactly "a string of at least one a", but for educational purposes it would be interesting to see a formal proof, which I can't produce.
  $endgroup$
  – Albert Hendriks
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can prove it directly on the regular expressions: Let $w in L(aa^ast)$, i.e. $w = a cdot u$ with $u in L(a^ast)$, i.e. $u = a^k$. for some $k in mathbbN$. Then $w = a^k+1 = a^k a in L(a^ast a)$. The other direction is analogous. However, for these simple expression you might also want to compute the corresponding NFAs and transform them to the minimal DFAs. If these DFAs coincide the regexes have also to be equivalent.
  $endgroup$
  – ttnick
  15 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @ttnick Converting to an NFA and then determinizing is much more work than just reasoning about what strings are matched.
  $endgroup$
  – David Richerby
  15 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ok this question confused me quite a bit since I read the title first and thought the "?" was part of the regex
  $endgroup$
  – Esben Skov Pedersen
  11 hours ago
  

  
  
  
  

 | 
show 2 more comments

1

1

$begingroup$

Let $Sigma = a, b$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

regular-expressions

share|cite|improve this question

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are equivalent because both accept exactly "a string of at least one a", but for educational purposes it would be interesting to see a formal proof, which I can't produce.
  $endgroup$
  – Albert Hendriks
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  16 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You can prove it directly on the regular expressions: Let $w in L(aa^ast)$, i.e. $w = a cdot u$ with $u in L(a^ast)$, i.e. $u = a^k$. for some $k in mathbbN$. Then $w = a^k+1 = a^k a in L(a^ast a)$. The other direction is analogous. However, for these simple expression you might also want to compute the corresponding NFAs and transform them to the minimal DFAs. If these DFAs coincide the regexes have also to be equivalent.
  $endgroup$
  – ttnick
  15 hours ago
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @ttnick Converting to an NFA and then determinizing is much more work than just reasoning about what strings are matched.
  $endgroup$
  – David Richerby
  15 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  ok this question confused me quite a bit since I read the title first and thought the "?" was part of the regex
  $endgroup$
  – Esben Skov Pedersen
  11 hours ago
  

  
  
  
  

 | 
show 2 more comments

$begingroup$

Let $Sigma = a, b$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.

regular-expressions

share|cite|improve this question

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

$endgroup$

share|cite|improve this question

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

share|cite|improve this question

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

edited 9 hours ago

Apass.Jack

12.9k1939

edited 9 hours ago

Apass.Jack

12.9k1939

asked 16 hours ago

YamahariYamahari

465

asked 16 hours ago

YamahariYamahari

465

1 Answer
1

active

oldest

votes

4

$begingroup$

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1dots w_ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1dots w_d$ matches $R$ and $w_d+1dots w_ell$ matches $S$. Here, $d=0$ and $d=ell$ mean that we've split $w$ into $varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1dots w_ell$ such that, for some $d$, $w_1dots w_d$ matches $a^*$ and $w_d+1dots w_ell$ matches $a$. We must have $d=ell-1$ and $w_ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w_1=dots=w_ell-1=a$ because that is the only length-$(ell-1)$ string that matches $a^*$. So $w=a^ell$ for some $ellgeq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^ell$ for some $ellgeq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^ell$ for $ellgeq 0$, and $a$ matches the single string $a=a^1$. So $a^*a$ matches any string $a^ell a$ for $ellgeq 0$, i.e., any string $a^ell+1$ for $ellgeq 0$, i.e., any string $a^ell$ for $ell>0$. Similarly, $aa^*$ matches any string $aa^ell=a^1+ell$ for $ellgeq 0$, i.e., $a^ell$ for $ell>0$.

share|cite|improve this answer

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

$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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcs.stackexchange.com%2fquestions%2f105689%2fare-regular-expressions-aa-and-aa-equivalent%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1dots w_ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1dots w_d$ matches $R$ and $w_d+1dots w_ell$ matches $S$. Here, $d=0$ and $d=ell$ mean that we've split $w$ into $varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1dots w_ell$ such that, for some $d$, $w_1dots w_d$ matches $a^*$ and $w_d+1dots w_ell$ matches $a$. We must have $d=ell-1$ and $w_ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w_1=dots=w_ell-1=a$ because that is the only length-$(ell-1)$ string that matches $a^*$. So $w=a^ell$ for some $ellgeq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^ell$ for some $ellgeq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^ell$ for $ellgeq 0$, and $a$ matches the single string $a=a^1$. So $a^*a$ matches any string $a^ell a$ for $ellgeq 0$, i.e., any string $a^ell+1$ for $ellgeq 0$, i.e., any string $a^ell$ for $ell>0$. Similarly, $aa^*$ matches any string $aa^ell=a^1+ell$ for $ellgeq 0$, i.e., $a^ell$ for $ell>0$.

share|cite|improve this answer

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

$endgroup$

add a comment | 

4

$begingroup$

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1dots w_ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1dots w_d$ matches $R$ and $w_d+1dots w_ell$ matches $S$. Here, $d=0$ and $d=ell$ mean that we've split $w$ into $varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1dots w_ell$ such that, for some $d$, $w_1dots w_d$ matches $a^*$ and $w_d+1dots w_ell$ matches $a$. We must have $d=ell-1$ and $w_ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w_1=dots=w_ell-1=a$ because that is the only length-$(ell-1)$ string that matches $a^*$. So $w=a^ell$ for some $ellgeq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^ell$ for some $ellgeq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^ell$ for $ellgeq 0$, and $a$ matches the single string $a=a^1$. So $a^*a$ matches any string $a^ell a$ for $ellgeq 0$, i.e., any string $a^ell+1$ for $ellgeq 0$, i.e., any string $a^ell$ for $ell>0$. Similarly, $aa^*$ matches any string $aa^ell=a^1+ell$ for $ellgeq 0$, i.e., $a^ell$ for $ell>0$.

share|cite|improve this answer

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

$endgroup$

add a comment | 

$begingroup$

Yes, they're equivalent. Informally, it's clear that "any number of $a$s followed by one more" is the same thing as "a $a$ followed by any number more." However, there was a request in the comments for something more formal so here goes...

If $R$ and $S$ are regular expressions, then the concatenation $RS$ matches any string $w=w_1dots w_ell$ (where the $w_i$ are the individual characters) such that, for some $d$, $w_1dots w_d$ matches $R$ and $w_d+1dots w_ell$ matches $S$. Here, $d=0$ and $d=ell$ mean that we've split $w$ into $varepsilon$ and $w$ and vice-versa.

So, consider $R=a^*$ and $S=a$. Then $RS$ matches any string $w=w_1dots w_ell$ such that, for some $d$, $w_1dots w_d$ matches $a^*$ and $w_d+1dots w_ell$ matches $a$. We must have $d=ell-1$ and $w_ell=a$ because only the string $a$ matches $a$, and it has length $1$. And we must have $w_1=dots=w_ell-1=a$ because that is the only length-$(ell-1)$ string that matches $a^*$. So $w=a^ell$ for some $ellgeq 1$.

Considering $R=a$ and $S=a^*$, an almost identical argument shows that any string that matches $aa^*$ must also be $a^ell$ for some $ellgeq 1$, so the two regular expressions do indeed match the same language.

At an intermediate level of formality, you can argue that $a^*$ matches any string $a^ell$ for $ellgeq 0$, and $a$ matches the single string $a=a^1$. So $a^*a$ matches any string $a^ell a$ for $ellgeq 0$, i.e., any string $a^ell+1$ for $ellgeq 0$, i.e., any string $a^ell$ for $ell>0$. Similarly, $aa^*$ matches any string $aa^ell=a^1+ell$ for $ellgeq 0$, i.e., $a^ell$ for $ell>0$.

share|cite|improve this answer

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

$endgroup$

share|cite|improve this answer

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 15 hours ago

David RicherbyDavid Richerby

68.5k15103194