# Count of "a"s and "b"s must be equal. Did you get it computer?

In the popular (and essential) computer science book, An Introduction to Formal Languages and Automata by Peter Linz, the following formal language is frequently stated:

$$\large{L=\{a^n b^n:n\in\mathbb{Z}^+\}}$$

mainly because this language can not be processed with finite-state automata. This expression mean "Language L consists all strings of 'a's followed by 'b's, in which the number of 'a's and 'b's are equal and non-zero".

# Challenge

Write a working program/function which gets a string, containing "a"s and "b"s only, as input and returns/outputs a truth value, saying if this string is valid the formal language L.

• Your program cannot use any external computation tools, including network, external programs, etc. Shells are an exception to this rule; Bash, e.g., can use command line utilities.

• Your program must return/output the result in a "logical" way, for example: returning 10 instead of 0, "beep" sound, outputting to stdout etc. More info here.

• Standard code golf rules apply.

This is a . Shortest code in bytes wins. Good luck!

### Truthy test cases

"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"


### Falsy test cases

""
"a"
"b"
"aa"
"ba"
"bb"
"aaa"
"aab"
"aba"
"abb"
"baa"
"bab"
"bba"
"bbb"
"aaaa"
"aaab"
"aaba"
"abaa"
"abab"
"abba"
"abbb"
"baaa"
"baab"
"baba"
"babb"
"bbaa"
"bbab"
"bbba"
"bbbb"


Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

/* Configuration */

var QUESTION_ID = 85994; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(a) {
});
comment_page = 1;
}
});
}

jQuery.ajax({
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
});
else process();
}
});
}

var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

function getAuthorName(a) {
return a.owner.display_name;
}

function process() {
var valid = [];

var body = a.body;
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});

var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
});

});

valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});

var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;

.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)

var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();

languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});

var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);

langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});

for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
language = jQuery(language);
jQuery("#languages").append(language);
}

}
body { text-align: left !important}

width: 290px;
float: left;
}

#language-list {
width: 290px;
float: left;
}

font-weight: bold;
}

table td {
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>

</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<tr><td>Language</td><td>User</td><td>Score</td></tr>
<tbody id="languages">

</tbody>
</table>
</div>
<table style="display: none">
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
</tbody>
</table>

• Can the input be empty? (You're saying it's not part of the language, but not whether it's an input we need to consider.) Jul 20, 2016 at 20:04
• What if our language doesn't have truthy or falsy? Would empty string == truthy and non-empty string == falsy be acceptable? Jul 20, 2016 at 20:20
• Nice challenge, but I think the title could be a little less ambiguous (i.e. a mention of a^n b^n or similar, rather than just the number of as equalling the number of bs) Jul 21, 2016 at 12:28
• @Sp3000 I choosed this title because it looked fun . I may change it later to sth else ...
– user55673
Jul 21, 2016 at 13:27
• I'm a little surprised that in 50+ answers I'm the only one to use a paser generator. To be sure it's not strictly competitive on length, but the problem posed is one of parsing a simple but non-trivial language. I'd very much like to see answers in other compiler-compiler syntaxes because I am not widely familiar with the choices. Jul 22, 2016 at 22:47

## Python 3, 32 bytes

eval(input().translate(")("*50))


Try it online!

Outputs via exit code: Error for false, no error for True.

The string is evaluated as Python code, replacing parens ( for a and ) for b. Only expressions of the form a^n b^n become well-formed expressions of parentheses like ((())), evaluating to the tuple ().

Any mismatched parens give an error, as will multiple groups like (()()), since there's no separator. The empty string also fails (it would succeed on exec).

The conversion ( -> a, ) -> b is done using str.translate, which replaces characters as indicated by a string that serves as a conversion table. Given the 100-length string ")("*50, the tables maps the first 100 ASCII values as

... Z[\]^_abc
... )()()()()(


which takes ( -> a, ) -> b.

In Python 2, conversions for all 256 ASCII values must be provided, requiring "ab"*128, one byte longer; thanks to isaacg for pointing this out.

Try it online! (Python 2, 33 bytes)

• Ok, that's clever.
– TLW
Jul 21, 2016 at 2:03
• What does the *128 do? Jul 22, 2016 at 22:17
• 128 can be replaced by 50 (or 99 for that matter) to save a byte. Jul 22, 2016 at 23:40
• @Eʀɪᴋ ᴛʜᴇ Gᴏʟғᴇʀ: I think it´s a quantifier. But I don´t really know Python and have not found any documentation on that yet. Jul 23, 2016 at 3:02
• @isaacg Thanks, I wasn't aware that changed for Python 3.
– xnor
Jul 23, 2016 at 6:43

# MATL, 5 4 bytes

tSP-


Prints a non-empty array of 1s if the string belongs to L, and an empty array or an array with 0s (both falsy) otherwise.

Thanks to @LuisMendo for golfing off 1 byte!

Try it online!

### How it works

t      Push a copy of the implicitly read input.
S     Sort the copy.
P    Reverse the sorted copy.
-   Take the difference of the code point of the corresponding characters
of the sorted string and the original.

• My second (working) MATL answer. :) Jul 21, 2016 at 0:49
• Strange definition of truthy and falsy: 'aabb' gives -1 -1 1 1 is truthy. 'aaabb' gives -1 -1 0 1 1 and is falsy Jul 25, 2016 at 8:02
• @Etoplay A non-empty array with all its values nonzero is truthy. It's the definition used in Matlab and Octave Jul 25, 2016 at 12:36

## Retina, 12 bytes

Credits to FryAmTheEggman who found this solution independently.

+a;?b
;
^;$ Prints 1 for valid input and 0 otherwise. Try it online! (The first line enables a linefeed-separated test suite.) ### Explanation Balancing groups require expensive syntax, so instead I'm trying to reduce a valid input to a simple form. Stage 1 +a;?b ;  The + tells Retina to repeat this stage in a loop until the output stops changing. It matches either ab or a;b and replaces it with ;. Let's consider a few cases: • If the as and the bs in the string aren't balanced in the same way that ( and ) normally need to be, some a or b will remain in the string, since ba, or b;a can't be resolved and a single a or b on its own can't either. To get rid of all the as and the bs there has to be one corresponding b to the right of each a. • If the a and the b aren't all nested (e.g. if we have something like abab or aabaabbb) then we'll end up with multiple ; (and potentially some as and bs) because the first iteration will find multiple abs to insert them and further iterations will preserve the number of ; in the string. Hence, if and only if the input is of the form anbn, we'll end up with a single ; in the string. Stage 2: ^;$


Check whether the resulting string contains nothing but a single semicolon. (When I say "check" I actually mean, "count the number of matches of the given regex, but since that regex can match at most once due to the anchors, this gives either 0 or 1.)

f s=s==[c|c<-"ab",'a'<-s]&&s>""


The list comprehension [c|c<-"ab",'a'<-s] makes a string of one 'a' for each 'a' in s, followed by one 'b' for each 'a' in s. It avoids counting by matching on a constant and producing an output for each match.

This string is checked to be equal to the original string, and the original string is checked to be non-empty.

• This is lovely. I often forget how useful it is that Haskell orders the elements of a list comprehension in a consistent and very specific way. Jul 21, 2016 at 19:31
• Much nicer than my best attempt (f=g.span id.map(=='a');g(a,b)=or a&&b==(not<$>a)) . Well done. Jul 22, 2016 at 21:04 • Wow, I didn't know one could match on a constant in a list comprehension! Jul 24, 2016 at 7:41 ## Grime, 12 bytes A=\aA?\b eA  Try it online! ## Explanation The first line defines a nonterminal A, which matches one letter a, possibly the nonterminal A, and then one letter b. The second line matches the entire input (e) against the nonterminal A. ## 8-byte noncompeting version e\a_?\b  After writing the first version of this answer, I updated Grime to consider _ as the name of the top-level expression. This solution is equivalent to the above, but avoids repeating the label A. • Why didn't you do it in J? Jul 20, 2016 at 19:38 • @LeakyNun I just wanted to show off Grime. :P Jul 20, 2016 at 19:39 • You built this language? Jul 20, 2016 at 19:40 • @LeakyNun Yes. Development is slow, but ongoing. Jul 20, 2016 at 19:41 # Brachylog, 23 19 bytes @2L,?lye:"ab"rz:jaL  Try it online! ### Explanation @2L, Split the input in two, the list containing the two halves is L ?lye Take a number I between 0 and the length of the input :"ab"rz Zip the string "ab" with that number, resulting in [["a":I]:["b":I]] :jaL Apply juxtapose with that zip as input and L as output i.e. "a" concatenated I times to itself makes the first string of L and "b" concatenated I times to itself makes the second string of L  • Congratulations on getting on tryitonline.net! Jul 20, 2016 at 20:01 # Bison/YACC 60 (or 29) bytes (Well, the compilation for a YACC program is a couple of steps so might want to include some for that. See below for details.) %% l:c'\n'; c:'a''b'|'a'c'b'; %% yylex(){return getchar();}  The function should be fairly obvious if you know to interpret it in terms of a formal grammar. The parser accepts either ab or an a followed by any acceptable sequence followed by a b. This implementation relies on a compiler that accepts K&R semantics to lose a few characters. It's wordier than I would like with the need to define yylex and to call getchar. Compile with $ yacc equal.yacc
$gcc -m64 --std=c89 y.tab.c -o equal -L/usr/local/opt/bison/lib/ -ly  (most of the options to gcc are specific to my system and shouldn't count against the byte count; you might want to count -std=c89 which adds 8 to the value listed). Run with $ echo "aabb" | ./equal


or equivalent.

The truth value is returned to the the OS and errors also report syntax error to the command line. If I can count only the part of the code that defines the parsing function (that is neglect the second %% and all that follows) I get a count of 29 bytes.

# 05AB1E, 9 bytes

Code:

.M{J¹ÔQ0r


Explanation:

.M         # Get the most frequent element from the input. If the count is equal, this
results into ['a', 'b'] or ['b', 'a'].
{        # Sort this list, which should result into ['a', 'b'].
J       # Join this list.
Ô      # Connected uniquified. E.g. "aaabbb" -> "ab" and "aabbaa" -> "aba".
Q     # Check if both strings are equal.
0r   # (Print 0 if the input is empty).


The last two bytes can be discarded if the input is guaranteed to be non-empty.

Uses the CP-1252 encoding. Try it online!.

• What happens with empty input? Jul 20, 2016 at 19:54
• Look for non-zero in the post; it’s in there :)
– Lynn
Jul 20, 2016 at 20:01
• @Lynn Doesn't the spec only say no-zero for a valid language though? Not about input. Jul 20, 2016 at 20:02
• True. Thought wrong there. But you can still do .M{J¹ÔQ0r for yours. Jul 20, 2016 at 20:17
• @Emigna Thanks, I have edited the post. Jul 20, 2016 at 20:20

# Jelly, 6 bytes

Ṣ=Ṛ¬Pȧ


Prints the string itself if it belongs to L or is empty, and 0 otherwise.

### How it works

Ṣ=Ṛ¬Pȧ  Main link. Argument: s (string)

Ṣ       Yield s, sorted.
Ṛ     Yield s, reversed.
=      Compare each character of sorted s with each character of reversed s.
¬    Take the logical NOT of each resulting Boolean.
P   Take the product of the resulting Booleans.
This will yield 1 if s ∊ L or s == "", and 0 otherwise.
ȧ  Take the logical AND with s.
This will replace 1 with s. Since an empty string is falsy in Jelly,
the result is still correct if s == "".


## Alternate version, 4 bytes (non-competing)

ṢnṚȦ


Prints 1 or 0. Try it online! or verify all test cases.

### How it works

ṢnṚȦ  Main link. Argument: s (string)

Ṣ     Yield s, sorted.
Ṛ   Yield s, reversed.
n    Compare each character of the results, returning 1 iff they're not equal.
Ȧ  All (Octave-style truthy); return 1 if the list is non-empty and all numbers
are non-zero, 0 in all other cases.


# J, 17 15 bytes

-2 bytes thanks to Jonah!

#<.2&#-:'ab'#~#


This works correctly for giving falsey for the empty string. Error is falsey.

Other versions:

<e.'ab'<@#"{~#\       NB. alternate 15 bytes, thanks to Jonah
#<.(-:'ab'#~-:@#)

NB. the following do not handle the empty string correctly
-:'ab'#~-:@#
2&#-:'ab'#~#          NB. thanks to miles


## Proof and explanation

Outdated, but applicable to the old 17 byte version.

The main verb is a fork consisting of these three verbs:

# <. (-:'ab'#~-:@#)


This means, "The lesser of (<.) the length (#) and the result of the right tine ((-:'ab'#~-:@#))".

The right tine is a 4-train, consisting of:

(-:) ('ab') (#~) (-:@#)


Let k represent our input. Then, this is equivalent to:

k -: ('ab' #~ -:@#) k


-: is the match operator, so the leading -: tests for invariance under the monadic fork 'ab' #~ -:@#.

Since the left tine of the fork is a verb, it becomes a constant function. So, the fork is equivalent to:

'ab' #~ (-:@# k)


The right tine of the fork halves (-:) the length (#) of k. Observe #:

   1 # 'ab'
'ab'
2 # 'ab'
'aabb'
3 # 'ab'
'aaabbb'
'ab' #~ 3
'aaabbb'


Now, this is k only on valid inputs, so we are done here. # errors for odd-length strings, which never satisfies the language, so there we are also done.

Combined with the lesser of the length and this, the empty string, which is not a part of our language, yields its length, 0, and we are done with it all.

• I modified it into 2&#-:'ab'#~# which should let you avoid the error and just output 0 instead while still using 12 bytes. Jul 20, 2016 at 21:33
• @miles Fascinating! I never thought about it like that. Jul 20, 2016 at 21:39
• Does this handle the empty string? Jul 21, 2016 at 11:24
• @Zgarb fixed it! Jul 21, 2016 at 19:30
• @Jonah Nice approaches! Jul 17 at 20:07

# JavaScript, 5455 44

s=>s&&s.match(^a{${l=s.length/2}}b{${l}}$)  Builds a simple regex based on the length of the string and tests it. For a length 4 string (aabb) the regex looks like: ^a{2}b{2}$

Returns a truthy or falsey value.

11 bytes saved thanks to Neil.

f=s=>s&&s.match(^a{${l=s.length/2}}b{${l}}$) // true console.log(f('ab'), !!f('ab')) console.log(f('aabb'), !!f('aabb')) console.log(f('aaaaabbbbb'), !!f('aaaaabbbbb')) // false console.log(f('a'), !!f('a')) console.log(f('b'), !!f('b')) console.log(f('ba'), !!f('ba')) console.log(f('aaab'), !!f('aaab')) console.log(f('ababab'), !!f('ababab')) console.log(f('c'), !!f('c')) console.log(f('abc'), !!f('abc')) console.log(f(''), !!f('')) • The f= can be omitted. Jul 20, 2016 at 19:53 • Is a function expression a valid submission, or must it actually be, ahem, functional? Jul 20, 2016 at 19:54 • A function is a valid submission. Jul 20, 2016 at 19:56 • @TimmyD It used to return true, but now it returns false. Jul 20, 2016 at 20:06 • s=>s.match(^a{${s.length/2}}b+$)? – l4m2 May 30, 2018 at 4:36 ## Perl 5.10, 35 17 bytes (with -n flag) say/^(a(?1)?b)$/


Ensures that the string starts with as and then recurses on bs. It matches only if both lengths are equal.

Thanks to Martin Ender for halving the byte count and teaching me a little about recursion in regexes :D

It returns the whole string if it matches, and nothing if not.

Try it here!

• Closest I can manage including the non-empty test case is 18 bytes: $_&&=y/a//==y/b// (requires -p), without the empty you could drop the && for 16! So close... Jul 21, 2016 at 9:08 • So I can do another 17 bytes: echo -n 'aaabbb'|perl -pe '$_+=y/a//==y/b//' but I can't shift another byte... Might have to give up on this! Jul 22, 2016 at 15:33
• Just realised that this could be done in 7 bytes using that regex as -F/^(a(?1)?b)$/: tio.run/##LYw9CoVADIT7nMNCCxGLV/pTeQwlAQtBdFHPb9yZPFgyk518k9Zr/… Apr 17, 2020 at 10:51 ## C, 57 53 Bytes t;x(char*s){t+=*s%2*2;return--t?*s&&x(s+1):*s*!1[s];}  Old 57 bytes long solution: t;x(char*s){*s&1&&(t+=2);return--t?*s&&x(s+1):*s&&!1[s];}  Compiled with gcc v. 4.8.2 @Ubuntu Thanks ugoren for tips! Try it on Ideone! • Since I'm new here and can't comment on other answers yet, I just want to point out that 62b solution from @Josh gives false positive on strings like "aaabab". Jul 22, 2016 at 15:47 • Change (t+=2) to t++++ for -1 byte. Jul 25, 2016 at 13:20 • @owacoder t++++ is not a valid C code. Jul 25, 2016 at 14:21 • Save some with t+=*s%2*2 and :*s*!1[s] Jul 31, 2016 at 14:18 • Very clever answer! It does unfortunately fail on input "ba" : ideone.com/yxixG2 – Josh Aug 8, 2016 at 15:07 # Vyxal, 765 4 bytes I÷<g  Try it Online! Try it Online! - without the f header Takes a list of characters as input. Outputs 1 for true for inputs in $$\\{a^n b^n:n∈\mathbb{Z}^+\}\$$, and empty string or 0 for false otherwise. This matches Vyxal's truthy/falsey semantics, which can be confirmed by putting ḃ (Boolify) in the Footer. I # Into Two Pieces - Splits a list into two halves and wraps them in a list. # If the input is odd in length, the left side gets 1 more character. ÷ # Item Split - Unwraps the list created above. Required so that the next # operation can compare the two halves. < # Less Than (vectorized) - Are items in the left half list less than the # corresponding items in the right half list? Puts 1 where yes, 0 where no. # The resulting list takes the size of whichever list was longer. For items # at the end of that list with no corresponding item in the other list, it # puts 0 if that position is empty in the right list, and 1 if it's empty in # the left list (which can never happen in this program). g # Minimum  Determining membership in $$\\{a^n b^n:n∈\mathbb{Z}^0\}\$$ can also be done in 4 bytes: I÷<A  Try it Online! Try it Online! - without the f header Takes a list of characters as input. Outputs 1 for true and 0 for false. Only the last element of the program is different: A # Check if all items in a list are truthy (returns truthy for an empty list)  # Vyxal, 65 4 bytes sṘ꘍g  Try it Online! Try it Online! - without the f: header Takes a list of characters as input. Outputs 1 for true for inputs in $$\\{a^n b^n:n∈\mathbb{Z}^+\}\$$, and empty string or 0 for false otherwise. This is a port of Dennis's MATL answer, with an algorithm also used by many subsequent answers. s # Pushes a copy of the input, sorted. Ṙ # Reverses the sorted copy. ꘍ # Levenshtein distance (vectorized) - Used here to compare corresponding # single-character strings between two lists, so it's effectively a vectorized # Not Equals, giving 1 for unequal and 0 for equal. This works around the fact # that Vyxal has no vectorizing Not Equals operator (even though it does have # vectorizing versions of all the other basic comparison operators). For input # in L, this will yield a non-empty list of all 1s. For an empty input it will # yield an empty list. For all other inputs it yields a list of both 1s and 0s. g # Minimum  To take a string as input, this becomes f:sṘ꘍g or alternatively fṘḂs꘍g (6 bytes). It is, however, possible to do this with the sort-and-reverse algorithm in 5 bytes (see AḂs꘍↓ below). Determining membership in $$\\{a^n b^n:n∈\mathbb{Z}^0\}\$$ can also be done in 4 bytes using this algorithm: sṘ꘍A  Try it Online! Try it Online! - without the f: header Takes a list of characters as input. Outputs 1 for true and 0 for false. To take a string as input, this becomes f:sṘ꘍A or alternatively fṘḂs꘍A (6 bytes). It is, however, possible to do this with the sort-and-reverse algorithm in 5 bytes (see AḂs꘍A below). # Vyxal, 5 bytes fI÷<g  Try it Online! Takes a string as input. Outputs 1 for true for inputs in $$\\{a^n b^n:n∈\mathbb{Z}^+\}\$$, and empty string or 0 for false otherwise. This is just one of the above 4 byte programs with f inserted at the beginning. Determining membership in $$\\{a^n b^n:n∈\mathbb{Z}^0\}\$$ can also be done in this way: fI÷<A  Try it Online! Takes a string as input. Outputs 1 for true and 0 for false. This too is just one of the above 4 byte programs with f inserted at the beginning – but it can also be done without f, using a conceptually similar algorithm: ½C÷‹⁼  Try it Online! Takes a string as input. Outputs 1 for true and 0 for false. ½ # Split in half. If odd in length, the left side gets 1 more character. This # creates a list containing two strings. C # Convert characters to their ASCII values. This results in a list containing # two lists of ASCII values. ÷ # Item Split - split the list into its elements on stack; in this case, these # are the left and right halves, each of which is a list of ASCII values. ‹ # Decrement - iff the right half is all 'b' (ASCII 98), this will change it to # all 'a' (ASCII 97) ⁼ # Are the two top items on the stack exactly equal? This gives a boolean value # that's 1 for true (equal counts of 'a' and 'b') and 0 for false.  # Vyxal, 5 bytes AḂs꘍↓  Try it Online! Takes a string as input. Outputs 1 for true, and empty string or 0 for false. This is an adaptation of the algorithm used in Dennis's Jelly answer and MATL answer (and many subsequent answers): A # Check if character is a vowel (vectorized) # Converts each 'a' to 1, and each 'b' to 0. Pushes the result as a list if # the input was a string of 2 characters or longer, but only pushes a single # integer if it was a single-character string. This limits what useful # operations can subsequently be done (for example, it can't be reliably # split into two halves). Ḃ # Bifurcate - Pushes the top of the stack then its reverse. s # Sort - Operates on the non-reversed copy. ꘍ # Bitwise Xor (vectorized) ↓ # Minimum by tail. On a list of numbers, it picks the item with the minimum # last digit. On a single number, it picks the minimum digit. Since the only # numbers given to it here will be 0 and 1, that's the same as the standard # minimum, except that it avoids the crash that happens with "g" (Minimum) # when its argument is not a list.  It appears to be impossible to solve this challenge in Vyxal in less than 5 bytes taking a string as input. Determining membership in $$\\{a^n b^n:n∈\mathbb{Z}^0\}\$$ can also be done in this way: AḂs꘍A  Try it Online! Takes a string as input. Outputs 1 for true and 0 for false. Only the last element of the program is different: A # Check if all items in a list are truthy (returns truthy for an empty list)  The purpose of this post is to demonstrate and explain the full list of golfed pure regexes that solve this challenge, and the range of compatibility of each among seven different regex engines, and rank them by length, all together in one post. Others' answers used the best regexes before this post; they are listed below. I ported the Java one to three other sets of regex engines, including Python 3's regex library. # Regex (Perl / PCRE / Boost / Pythonregex), 11 bytes ^(a(?1)?b)$


Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Boost
Try it online! - Python import regex

Included for completeness. Already used in:

^          # Assert we're at the beginning of the string.
(          # Define subroutine (?1):
a      # Match one 'a'.
(?1)?  # Optionally do a recursive subroutine call to (?1).
b      # Match one 'b'.
)
$# Assert we're at the end of the string.  When the regex engine hits the (?1)?, it has the choice of whether to do the call or not. Due to ? being greedy by default, it first tries doing the call; if it then hits a b character instead of an a, it will backtrack, avoid doing the subroutine call, and then reach the part of the regex that matches a b character. From that point forward, it will keep popping out of the recursive call stack, matching another b each time. This way, the number of times that it attempts to match b equals the number of a it matched at the beginning. If it finds an a when attempting to match b, this will trigger a non-match. If it finishes popping and still finds more b characters, this will trigger a non-match at the $ part of the regex. If it reaches the end of the string prematurely during this stage, it will pop out from that call and attempt to match another b, thus triggering a non-match.

The only backtracking left to be tried at the popping-out stage, in the case of any of those non-matches, is to stop calling (?1) at an earlier point, but this will also fail to match, as it will then be trying to match a where the string has a b; this will result in a top-level non-match.

^(a\g<1>?b)$ Try it online! - PCRE1 Try it online! - PCRE2 Try it online! - Ruby Included for completeness. Already used in G B's Ruby answer. This is the same as the 11 byte version, but using Ruby's subroutine call syntax. # Regex (Perl / PCRE / Java), 21 bytes ^(a(?=a*(\2?+b)))+\2$


Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java

Turned out to be used in Kevin Cruijssen's Java answer, but gave it a -6 byte golf.

This regex is the next-best thing to recursion, in engines that lack it. It works using group-building:

^           # Assert we're at the beginning of the string.
(
a       # Match one more 'a' per each iteration of this loop.
# Lookahead assertion - when this finishes, the regex engine's "cursor"
# will jump back to the same position as it was in when it entered the
# lookahead here. It's atomic, so the regex engine can't backtrack into
# the lookahead once it has completed its match or non-match. This means
# the main loop will exit immediately if this lookahead fails to match
# (due to running out of 'b' characters to match), or if the 'a' above
# fails to match.
(?=
a*      # Skip over as many 'a' as necessary to get to the first 'b'.
# Capture \2, embedding within it the previous contents of itself.
# If this is the first iteration, \2 will be unset, so capture a
# single 'b' in \2. Otherwise, append one more 'b' to the previous
# contents of \2.
(
\2?+    # Optionally match \2, but if it does match, lock that
# match in (don't backtrack to here and try not making the
# match, in the case that a non-match occurs after this
# point). This is guaranteed to fail to match if and only if
# we're on the first iteration, due to \2 being unset. On
# subsequent iterations, since \2 will have been captured
# starting at the first non-'a' character, and always starts
# its attempted match there, it will be guaranteed to match.
b       # Match one 'b'.
)
)
)+
\2          # Match however many 'b' we captured in \2.
$# Assert we're at the end of the string.  # Regex (.NET), 22 bytes ^(a)+(?<-1>b)+$(?(1)^)


Try it online!

Included for completeness. Already used in:

This regex uses the Balancing Groups feature of the .NET regex engine:

^           # Assert we're at the beginning of the string.

(a)+        # Match as many 'a' characters as we can, minimum of one, pushing
# each single-character capture onto the Group 1 capture stack.

(?<-1>b)+   # Pop the Group 1 capture stack as many times as we can, matching
# a single 'b' each time. This will stop looping when it hits a
# character other than 'b', or empties the Group 1 capture stack.

$# Assert we're at the end of the string. If this fails to match # (meaning there are more 'b' characters than 'a' characters), the # regex engine will backtrack, but none of the choices it has will # be able lead to a match, so there will be a top-level non-match. (?(1)^) # If there are any remaining captures on the Group 1 stack (which # means there were fewer 'b' characters than 'a' chracters), assert # something which can never be true - that we're at the beginning # of the string. Since the first thing the regex did was capture at # least one 'a', the fact that we've reached this point means that # was already done, so it's impossible for us to be at the beginning # of the string. Thus this causes a non-match in the case that there # are fewer 'b' than 'a'.  Some people use this regex in the form of ^(a)+(?<-1>b)+(?(1)^)$, i.e. with the $ at the end rather than the beginning, but I prefer ^(a)+(?<-1>b)+$(?(1)^), since it tries the slightly-less-complicated operation of $ first, so in the case of a non-match, it will be ever so slightly more efficient. In theory. The ^ in the (?(1)^) can be replaced with various other things that can't match, such as (?(1).) or (?(1)c). # Regex (Perl / PCRE / Java / .NET), 24 bytes ^(a(?=a*((?>\2?)b)))+\2$


Try it online! - Perl
Try it online! - PCRE1
Try it online! - PCRE2
Try it online! - Java
Try it online! - .NET

This is a port of the 21 byte Perl/PCRE/Java regex, with \3?+ changed to (?>\3?) to allow the regex to also work on .NET (which lacks possessive quantifiers).

# Regex (Perl / PCRE / Java / Ruby / Pythonregex), 29 bytes

^(a(?=a*(?=(\3?+b))(\2)))+\2$ Try it online! - Perl Try it online! - PCRE1 Try it online! - PCRE2 Try it online! - Java Try it online! - Ruby Try it online! - Python import regex This is a port of the 21 byte Perl/PCRE/Java regex (see below) adding compatibility with engines that lack nested backreferences, but still have forward-declared backreferences and possessive quantifiers. This allows it to work in Python when using the regex library instead of re. ^ # Assert we're at the beginning of the string. ( a # Match one 'a' per iteration of this loop. (?= a* # Skip over as many 'a' as necessary to get to the first 'b'. (?= # Capture \2. If this is the first iteration, \3 will be unset, so # capture a single 'b' in \2. Otherwise, \2 = \3 concatenated with # one more 'b'. ( \3?+ b ) ) # \3 = make a copy of \2, which was captured above ( \2 ) ) )+ \2 # Match however many 'b' we captured in \2.$           # Assert we're at the end of the string.


^(a(?=a*(?=((?>\3?)b))(\2)))+\2$ Try it online! - Perl Try it online! - PCRE1 Try it online! - PCRE2 Try it online! - Java Try it online! - Ruby Try it online! - Python import regex Try it online! - .NET This is a port of the above, with \3?+ changed to (?>\3?) to allow the regex to work on .NET (which lacks possessive quantifiers), so it can support 6 different regex engines at once. It is not supported by Boost, which lacks both forward-declared and nested backreferences. It might not be possible for a single regex to work on all 7 engines. # Retina, 22 bytes Another shorter answer in the same language just came... ^(a)+(?<-1>b)+(?(1)c)$


Try it online!

This is a showcase of the balancing groups in regex, which is explained fully by Martin Ender.

As my explanation would not come close to half of it, I'll just link to it and not attempt to explain, as that would be detrimental to the glory of his explanation.

# Befunge-93, 67 bytes

0v@.<  0<@.!-$< >0\v +>~:0!#^_:"a" -#^_$ 1
~+1_^#!-"b" _ ^#0: <


Try it here! Might explain how it works later. Might also try to golf it just a tad bit more, just for kicks.

## Mathematica, 45 bytes

#~StringMatchQ~RegularExpression@"(a(?1)?b)"&


Another recursive regex solution. This doesn't need anchors because StringMatchQ achors it implicitly, but unfortunately it just seems to do wrap the regex in ^(?:...)$ which means we can't use (?R) for the recursion, as that gets the anchors as well. Hence the seemingly useless group around the entire regex, so we can access only that part for the recursion. # C, 69 bytes 69 bytes: #define f(s)strlen(s)==2*strcspn(s,"b")&strrchr(s,97)+1==strchr(s,98) For those unfamiliar: • strlen determines the length of the string • strcspn returns the first index in string where the other string is found • strchr returns a pointer to the first occurrence of a character • strrchr returns a pointer to the last occurrence of a character A big thanks to Titus! • save one byte with >97 instead of ==98 Jul 23, 2016 at 2:02 • 61 bytes solution gives false positive on strings like "aaabab". See ideone.com/nmT8rm Jul 28, 2016 at 16:36 • Ah you are correct Jasmes, thanks. I will have to rethink this a little. – Josh Jul 28, 2016 at 17:30 • Reverting back to the 69 byte solution, not sure if I can get any shorter using this approach. – Josh Jul 28, 2016 at 19:45 # MATL, 9 bytes vHI$e!d1=


Try it online!

The output array is truthy if it is non-empty and all its entries are nonzero. Otherwise it's falsy. Here are some examples.

v     % concatenate the stack. Since it's empty, pushes the empty array, []
H     % push 2
I$% specify three inputs for next function e % reshape(input, [], 2): this takes the input implicitly and reshapes it in 2 % columns in column major order. If the input has odd length a zero is padded at % the end. For input 'aaabbb' this gives the 2D char array ['ab;'ab';'ab'] ! % transpose. This gives ['aaa;'bbb'] d % difference along each column 1= % test if all elements are 1. If so, that means the first tow contains 'a' and % the second 'b'. Implicitly display  • That's some convenient definition of truthy. (I knew about the non-zero requirement, but not about the non-empty one.) Jul 21, 2016 at 0:34 # x86 machine code, 29 27 bytes Hexdump: 33 c0 40 41 80 79 ff 61 74 f8 48 41 80 79 fe 62 74 f8 0a 41 fe f7 d8 1b c0 40 c3  Assembly code:  xor eax, eax; loop1: inc eax; inc ecx; cmp byte ptr [ecx-1], 'a'; je loop1; loop2: dec eax; inc ecx; cmp byte ptr [ecx-2], 'b'; je loop2; or al, [ecx-2]; neg eax; sbb eax, eax; inc eax; done: ret;  Iterates over the a bytes in the beginning, then over the following 'b' bytes. The first loop increases a counter, and the second loop decreases it. Afterwards, does a bitwise OR between the following conditions: 1. If the counter is not 0 at the end, the string doesn't match 2. If the byte that follows the sequence of bs is not 0, the string also doesn't match Then, it has to "invert" the truth value in eax - set it to 0 if it was not 0, and vice versa. It turns out that the shortest code to do that is the following 5-byte code, which I stole from the output of my C++ compiler for result = (result == 0):  neg eax; // negate eax; set C flag to 1 if it was nonzero sbb eax, eax; // subtract eax and the C flag from eax inc eax; // increase eax  • I think you can improve your negation. Try: neg eax to set the carry flag as before, cmc to invert the carry flag and salc to set AL to FFh or 0 depending on whether the carry flag is set or not. Saves 2 bytes, although does end up with an 8-bit result rather than 32-bit. Jul 22, 2016 at 21:40 • The same thing using string ops, with ESI pointing to the input string, and returning the result in AL (uses SETcc, requires 386+): xor eax,eax | xor ecx,ecx | l1: inc ecx | lodsb | cmp al, 'a' | jz l1 | dec esi | l2: lodsb | cmp al,'b' | loopz l2 | or eax,ecx | setz al | ret Jul 26, 2016 at 21:26 • @ninjalj You should post that in an answer - it's sufficiently different from mine, and I suspect is significantly shorter! Jul 26, 2016 at 22:02 # Ruby, 24 bytes eval(gets.tr'ab','[]')*1  (This is just xnor's brilliant idea in Ruby form. My other answer is a solution I actually came up with myself.) The program takes the input, transforms a and b to [ and ] respectively, and evaluates it. Valid input will form a nested array, and nothing happens. An unbalanced expression will make the program crash. In Ruby empty input is evaluated as nil, which will crash because nil has not defined a * method. # Sed, 38 + 2 = 40 bytes s/.*/c&d/;:x;s/ca(.*)bd/c\1d/;tx;/cd/p  A non empty string output is truthy Finite state automata can not do this, you say? What about finite state automata with loops. :P Run with r and n flags. ### Explanation s/.*/c&d/ #Wrap the input in 'c' and 'd' (used as markers) :x #Define a label named 'x' s/ca(.*)bd/c\1d/ #Deletes 'a's preceded by 'c's and equivalently for 'b's and 'd's. This shifts the markers to the center tx #If the previous substitution was made, jump to label x /cd/p #If the markers are next to one another, print the string  • Nice approach. Thanks for the breakdown. Jul 25, 2016 at 3:28 # JavaScript, 44 42 Crossed out 44 is still regular 44 ;( f=s=>(z=s.match^a(.+)b$)?f(z[1]):s=="ab"


Works by recursively stripping off the outer a and b and recursively using the inner value selected but .+. When there's no match on ^a.+b$ left, then the final result is whether the remaining string is the exact value ab. Test cases: console.log(["ab","aabb","aaabbb","aaaabbbb","aaaaabbbbb","aaaaaabbbbbb"].every(f) == true) console.log(["","a","b","aa","ba","bb","aaa","aab","aba","abb","baa","bab","bba","bbb","aaaa","aaab","aaba","abaa","abab","abba","abbb","baaa","baab","baba","babb","bbaa","bbab","bbba","bbbb"].some(f) == false)  # ANTLR, 31 bytes grammar A;r:'ab'|'a'r'b'|r'\n';  Uses the same concept as @dmckee's YACC answer, just slightly more golfed. To test, follow the steps in ANTLR's Getting Started tutorial. Then, put the above code into a file named A.g4 and run these commands: $ antlr A.g4
$javac A*.java  Then test by giving input on STDIN to grun A r like so: $ echo "aaabbb" | grun A r


If the input is valid, nothing will be output; if it is invalid, grun will give an error (either token recognition error, extraneous input, mismatched input, or no viable alternative).

Example usage:

$echo "aabb" | grun A r$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}

• Clever trick adding the newline as an alternate in a single rule. I think I could save a few that way in yacc, too. The grammer keyword is a stinker for golfing with antlr, though. Kinda like using fortran. Jul 28, 2016 at 16:15

## R, 6461 55 bytes, 73 67 bytes (robust) or 46 bytes (if empty strings are allowed)

1. Again, xnor's answer reworked. If it is implied by the rules that the input will consist of a string of as and bs, it should work: returns NULL if the expression is valid, throws and error or nothing otherwise.

if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))

2. If the input is not robust and may contain some garbage, e.g. aa3bb, then the following version should be considered (must return TRUE for true test cases, not NULL):

if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))

3. Finally, if empty strings are allowed, we can ignore the condition for non-empty input:

eval(parse(text=chartr("ab","{}",scan(,''))))


Again, NULL if success, anything else otherwise.

• I don´t know R, what´s your result for empty input? (should be falsy) Jul 23, 2016 at 2:35
• Is there really no shorter way to test for empty input? Jul 25, 2016 at 6:58
• Version 1: just nothing (correct input returns only NULL), version 2: just nothing (correct input returns only TRUE), version 3 (assuming empty strings are OK, as state): NULL. R is a statistical object-oriented language that typecasts everything just OK, without any warning. Jul 26, 2016 at 11:24
• This (answer 1) can be further improved to 55 bytes: if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y))) Aug 4, 2017 at 14:01

# Japt, 11 bytes

©¬n eÈ¦Ug~Y


Try it online!

Gives either true or false, except that "" gives "" which is falsy in JS.

### Unpacked & How it works

U&&Uq n eXYZ{X!=Ug~Y

U&&     The input string is not empty, and...
Uq n    Convert to array of chars and sort
eXYZ{   Does every element satisfy...?
X!=       The sorted char does not equal...
Ug~Y      the char at the same position on the original string reversed


# Prolog (SWI), 34 33 bytes

-[].
-L:-append([97|M],b,L),-M.


Try it online!

# Brachylog (newer), 1110 6 bytes

o?ḅĊlᵛ


Try it online!

The predicate succeeds if the input is in L and fails otherwise.

          The input
o         sorted
?        is the input,
ḅ       and the runs in the input
Ċ      of which there are two
lᵛ    have the same length.

• At this rate you will catch up to my number of Brachylog answers in a few days! Mar 1, 2019 at 12:17
• That use of ᵛ is really clever! Feb 16 at 22:32
• @DLosc Thanks! z₂ didn't exist yet ;) Feb 16 at 23:09

# 05AB1E, 6 bytes

ÇÂs{αß


Only 1 is truthy in 05AB1E, and it'll output 0 (or "" for the empty string) as falsey.

Explanation:

Ç       # Convert the (implicit) input-string to a list of integer codepoints
#  i.e. "aaabbb" → [97,97,97,98,98,98]
#  i.e. "baba" → [98,97,98,97]
#  i.e. "aab" → [97,97,98]
#  i.e. "" → []
Â      # Bifurcate this list (short for Duplicate & Reverse copy)
#  STACK: [[97,97,97,98,98,98], [98,98,98,97,97,97]]
#  STACK: [[98,97,98,97], [97,98,97,98]]
#  STACK: [[97,97,98], [98,97,97]]
#  STACK: [[], []]
s     # Swap to get the duplicated list
#  STACK: [[98,98,98,97,97,97], [97,97,97,98,98,98]]
#  STACK: [[97,98,97,98], [98,97,98,97]]
#  STACK: [[98,97,97], [97,97,98]]
#  STACK: [[], []]
{    # Sort it
#  STACK: [[98,98,98,97,97,97], [97,97,97,98,98,98]]
#  STACK: [[97,98,97,98], [97,97,98,98]]
#  STACK: [[98,97,97], [97,97,98]]
#  STACK: [[], []]
α   # Take the absolute difference at the same positions
#  STACK: [[1,1,1,1,1,1]]
#  STACK: [[0,1,1,0]]
#  STACK: [[1,0,1]]
#  STACK: [[], []]
ß  # And take the minimum, which will be 1 if all were truthy;
# 0 if any were falsey; or an empty string if the list is empty
#  STACK: [1]
#  STACK: [0]
#  STACK: [0]
#  STACK: [""]
# (after which it is output implicitly as result)
`