Hfrxdjt

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?

Help rendering a complicated sum/product formula

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

Do US professors/group leaders only get a salary, but no group budget?

When did antialiasing start being available?

Describing a chess game in a novel

Recruiter wants very extensive technical details about all of my previous work

What does Jesus mean regarding "Raca," and "you fool?" - is he contrasting them?

Can a wizard cast a spell during their first turn of combat if they initiated combat by releasing a readied spell?

Print a physical multiplication table

I got the following comment from a reputed math journal. What does it mean?

gerund and noun applications

Right piano pedal is bright

Why is there so much iron?

Pronounciation of the combination "st" in spanish accents

Wrapping homogeneous Python objects

Unfrosted light bulb

Is it insecure to send a password in a `curl` command?

What does "mu" mean as an interjection?

Could Sinn Fein swing any Brexit vote in Parliament?

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

Turning a hard to access nut?

I seem to dance, I am not a dancer. Who am I?

Is there a creature that is resistant or immune to non-magical damage other than bludgeoning, slashing, and piercing?

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 6 hours ago

Apass.Jack

12.9k1939

asked 13 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
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  13 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
  12 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
  12 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
  9 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 6 hours ago

Apass.Jack

12.9k1939

asked 13 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
  13 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  13 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
  12 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
  12 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
  9 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 6 hours ago

Apass.Jack

12.9k1939

asked 13 hours ago

YamahariYamahari

465

$endgroup$

share|cite|improve this question

edited 6 hours ago

Apass.Jack

12.9k1939

asked 13 hours ago

YamahariYamahari

465

share|cite|improve this question

edited 6 hours ago

Apass.Jack

12.9k1939

asked 13 hours ago

YamahariYamahari

465

edited 6 hours ago

Apass.Jack

12.9k1939

edited 6 hours ago

Apass.Jack

12.9k1939

asked 13 hours ago

YamahariYamahari

465

asked 13 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 12 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 12 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 12 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 12 hours ago

David RicherbyDavid Richerby

68.5k15103194

$endgroup$

share|cite|improve this answer

answered 12 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 12 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 12 hours ago

David RicherbyDavid Richerby

68.5k15103194