Mdtryhht

Can a medieval gyroplane be built?

Is there a term for accumulated dirt on the outside of your hands and feet?

Why are there no stars visible in cislunar space?

PTIJ: Why do we blow Shofar on Rosh Hashana and use a Lulav on Sukkos?

Using Past-Perfect interchangeably with the Past Continuous

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

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

Probably overheated black color SMD pads

Print last inputted byte

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

Does the attack bonus from a Masterwork weapon stack with the attack bonus from Masterwork ammunition?

How do hiring committees for research positions view getting "scooped"?

두음법칙 - When did North and South diverge in pronunciation of initial ㄹ?

Help prove this basic trig identity please!

Calculate the frequency of characters in a string

Practical application of matrices and determinants

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

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

What is the term when voters “dishonestly” choose something that they do not want to choose?

In Aliens, how many people were on LV-426 before the Marines arrived​?

PTIJ What is the inyan of the Konami code in Uncle Moishy's song?

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

What does "^L" mean in C?

gerund and noun applications

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

Apass.Jack

12.9k1939

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

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  15 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
  14 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
  14 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 8 hours ago

Apass.Jack

12.9k1939

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

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  me neither, that's why I am not sure
  $endgroup$
  – Yamahari
  15 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
  14 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
  14 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 8 hours ago

Apass.Jack

12.9k1939

asked 15 hours ago

YamahariYamahari

465

$endgroup$

share|cite|improve this question

edited 8 hours ago

Apass.Jack

12.9k1939

asked 15 hours ago

YamahariYamahari

465

share|cite|improve this question

edited 8 hours ago

Apass.Jack

12.9k1939

asked 15 hours ago

YamahariYamahari

465

edited 8 hours ago

Apass.Jack

12.9k1939

edited 8 hours ago

Apass.Jack

12.9k1939

asked 15 hours ago

YamahariYamahari

465

asked 15 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 14 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 14 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 14 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 14 hours ago

David RicherbyDavid Richerby

68.5k15103194

$endgroup$

share|cite|improve this answer

answered 14 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 14 hours ago

David RicherbyDavid Richerby

68.5k15103194

answered 14 hours ago

David RicherbyDavid Richerby

68.5k15103194