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:


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".


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


Falsy test cases

  • 24
    \$\begingroup\$ 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.) \$\endgroup\$ – Martin Ender Jul 20 '16 at 20:04
  • 1
    \$\begingroup\$ What if our language doesn't have truthy or falsy? Would empty string == truthy and non-empty string == falsy be acceptable? \$\endgroup\$ – DJMcMayhem Jul 20 '16 at 20:20
  • 5
    \$\begingroup\$ 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) \$\endgroup\$ – Sp3000 Jul 21 '16 at 12:28
  • 1
    \$\begingroup\$ @Sp3000 I choosed this title because it looked fun . I may change it later to sth else ... \$\endgroup\$ – user55673 Jul 21 '16 at 13:27
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – dmckee Jul 22 '16 at 22:47

84 Answers 84


Octave, 28 bytes


This defines an anonymous function. It works also for empty input. Falsy and truthy are as described in my MATL answer.

Try it at ideone.


diff(+m)>0 checks if the input string (consisting of 'a' and 'b') is sorted, that is, all characters 'a' come before all 'b'.

The other condition that needs to be checked is whether the numbers of characters 'a' and 'b' are the same. Since their ASCII codes are 97 ansd 98, this is done subtracting 97.5 and chacking if the the sum is zero.

For empty input the result is empty, which is falsy.


Mathematica, 45 bytes


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.


Mathematica 83 80 68 54 bytes


Thanks @MartinEnder for shortening it by 26 bytes :)

If input can be a list of characters instead of a string, 39 bytes is possible:




  • 1
    \$\begingroup\$ It's probably shortest with a recursive regex: #~StringMatchQ~RegularExpression@"(a(?1)?b)"& \$\endgroup\$ – Martin Ender Jul 21 '16 at 9:41
  • \$\begingroup\$ @MartinEnder Ah yes - much better - I'll delete & let you post that, since it doesn't resemble my awful attemp in the slightest! \$\endgroup\$ – martin Jul 21 '16 at 9:43
  • 1
    \$\begingroup\$ No, don't delete yours. A regex-less solution is still interesting. :) \$\endgroup\$ – Martin Ender Jul 21 '16 at 9:43

JavaScript, 34 bytes


In true automata fashion, this function returns 1 if it's true, and fails if it's not.


let test_strings = ["ab", "aabb", "", "a", "abb", "abc", "abab", "abba"];
test_strings.map(s => {
try {console.log("f(\"" + s + "\") returned " + f(s));}
catch(e) {console.log("f(\"" + s + "\") threw " + e);}


Excel, 55 bytes


Test string in cell A1, formula above in any other cell. Generates a comparison string of the appropriate length and checks for a match. Shows TRUE or FALSE as appropriate.


PHP, 61 40 bytes

new approach inspired by Didz´ answer: regexp with a recursive pattern


P.S.: I see now that I am not the first one with this pattern. You never stop learning.

Josh´s C solution translated to PHP comes at the same size (with one byte lost in translation, one byte golfed for PHP with bitwise and, one byte golfed for C and PHP):

<?=strlen($s=$argv[1])==2*strspn($s,a)&$s[strrpos($s,a)+1]>a; (61 bytes)

My second own approach, a little longer: build a string with (input length / 2) of a, one of b and compare the concatenation to input:
<?=str_repeat(a,$n=strlen($s=$argv[1])/2).str_repeat(b,$n)==$s; (63 bytes)
Could save 3 bytes on that if I could use ($r=str_repeat) for a function call directly ... if.

all versions:

  • take the string as argument from cli
  • print 1 for true, nothing for false


  • replace <?= with <?function f($s){return
  • remove =$argv[1] (or replace $argv[1] with $s)
  • append } and my test suite (below)
  • call in a web browser

function out($a){if(is_object($a)){foreach($a as$v)$r[]=$v;return'{'.implode(',',$r).'}';}if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',$e==$y?'Y':'N',"</td></tr>";$h='';}
foreach($cases as$e=>$a)foreach($a as$x)test($x,$e,f($x)|0);

TI-Basic, 35 bytes

Zero is True; anything else is False.

Input Str1
inString(Str1,"a",Ans) or Ans≠inString(Str1,"b


Input Str1                 Get string into Str1
1+.5length(Str1            Get number that is one more than half. For example, 8 gives 5.
inString(Str1,"a",Ans)     Yields zero if there is no instances of a in the second half
                               (using the number we just calculated as the start point for the search)
 or                        Both conditions need to be zero in order to output zero
Ans≠inString(Str1,"b       Yields zero if the first instance of b is the number we calculated earlier
  • \$\begingroup\$ I think you might be confused... parentheses don't have to be closed in TI-Basic. Thanks for the concern, though. \$\endgroup\$ – Timtech Jul 28 '16 at 16:38
  • \$\begingroup\$ You're not using TI-Basic's notion of truthy/falsy here. How is that allowed? \$\endgroup\$ – Jakob Aug 29 '17 at 19:24
  • 1
    \$\begingroup\$ I answered this a while ago, and it seems that we could specify which outputs indicated true or false. But, in accordance with your suggestion you could add not( to the beginning of the last line. \$\endgroup\$ – Timtech Aug 29 '17 at 23:08

C, 65 bytes

  • \$\begingroup\$ m---- doesn't compile. \$\endgroup\$ – ugoren Jul 31 '16 at 14:33
  • \$\begingroup\$ @ugoren what compiler are you using? \$\endgroup\$ – Stefano Sanfilippo Aug 8 '16 at 9:31
  • \$\begingroup\$ gcc on Linux says error: invalid lvalue in decrement. Does any compiler compile this? \$\endgroup\$ – ugoren Aug 8 '16 at 14:56
  • \$\begingroup\$ Whoopsie, correct, nice catch @ugoren, I must have missed the error among the warnings. Reverted to the 65 byte solution. \$\endgroup\$ – Stefano Sanfilippo Aug 10 '16 at 9:09

Cubically, 109 98 70 60 bytes


-11 bytes thanks to TehPers

-10 bytes thanks to new language feature

Try it online!

Prints 1 if the string matches L, otherwise prints nothing.


+52/1+55            Sets the notepad to 97 ('a')
        ~           takes input
         =7!6&      exits if input is not 'a'

(             )6    While the notepad is truthy
 :7                 Save the current character value
   UR'UF'D2         Perform a cube operation
           ~=7      Set notepad to true if next character is the same

>7?6&               Exit if next character is end of input (-1)

(             )6    While the notepad is truthy
 :7                 Save the current character
   D2FU'RU'         Reverse one iteration of the previous operation
            ~=7     Set notepad to true if next character is the same

>7!6&               Exit if next character is NOT end of input
!8%6                Print 1 if the cube is solved

The looping operation has been replaced with a new sequence with a period of 1260, which will still never give a false negative but now is guaranteed to work for inputs of less than 1260 characters.

I've replaced the previous check for solved cube with !8%6. 8 is a recently added pseudo-face which is always equal to "Is the cube solved?" so I can just branch on that directly.

  • \$\begingroup\$ Why not do -6>7?6& instead of -6>7!6{...}? Also, couldn't you replace -6+111=3!6& with -6+21=3!6&, -6+1111=4!6& with -6+22=4!6&, and -6+11111=5!6& with -6+32=5!6&? You checked those faces earlier in the program. Also, you can replace -6=0!6& with -6>0?6& and remove the next -6 because 0 isn't greater than 0. Rather than =#!6&-6..., try =#0?6&.... I'm also pretty sure you can remove one or two of those checks, but I'm not a mathematician. I had a solution similar to this in mind, but I didn't think to compare the notepad to the previous value. Nice job! \$\endgroup\$ – TehPers Aug 7 '17 at 21:10
  • \$\begingroup\$ Also, you can remove the -6 in -6=0!6& because to exit the loop before it, the notepad must be 0. \$\endgroup\$ – TehPers Aug 7 '17 at 21:15

Brachylog (newer), 11 10 6 bytes


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.
  • 1
    \$\begingroup\$ At this rate you will catch up to my number of Brachylog answers in a few days! \$\endgroup\$ – Fatalize Mar 1 at 12:17

Nearly 5 months later, decided to come back to my first answer here to see if I could golf it more. Here's the results!

Zsh, 28 bytes

eval ${${${1:?}//a/( }//b/)}

Just as I posted my 29 byte answer, I thought "what about if we handle the empty case specially?" Turns out, it's one byte shorter! Try it online!

Successful cases: ( ( ( ... ( ( ))...))).

Unsuccessful cases:

  • Unmatched/uneven parens: obviously fails
  • /ba/ case: ( )( ) is a "parse error" in the eval, but gives unknown file attribute: if run directly.
  • Empty case: ${1:?} handles exactly this.

Zsh, 29 bytes

eval \(${${1//a/(+}//b/+i)}\)

Try it online!

Same "eval matching delimiters" principle, but this time using math mode instead of parameter expansions:

eval \(${${1//a/(+}//b/+i)}\)
     \(                    \)   # literal ( )
         ${1//a/(+}             # replace 'a' with '(+'
       ${          //b/+i)}     # replace 'b' with '+i)'

A successful result looks like: ((+(+(...+(++i)+...i)+i)+i)), incrementing i to 1 and adding it repeatedly. This will result in a positive integer, which (( )) evaluates truthy.

An unsuccessful result looks like one of the following:

  • Uneven/unmatched parens (obviously fails)
  • /^b(a{n}b{n})?a$/ case: (+i)(...)(+) fails with "missing identifier after +"
  • Any other /ba/ case: (...)(...) errors in math mode
  • Empty case: () is an anonymous function with no body, and errors

Original answer:

Zsh, 35 bytes

eval '${'${${1//a/'${'}//b/'}'}'#}'

Try it online! (More examples)

Inspired by xnor's post, this outputs via exit code. Zsh will happlily handle nested ${}s, but will err on ${${...}${...}} or unmatched braces. There are two caveats which makes this longer:

  • We need the outer ${...}, since ${}${} is valid zsh.
  • We need a # at then end, which causes an error when the input is the empty string:
    • ${${}#} is prefix removal, which is fine.
    • ${#} evaluates to the number of parameters, which will be an integer and not a valid command.
  • 1
    \$\begingroup\$ Welcome to PPCG! Nice first answer \$\endgroup\$ – Jo King Mar 21 at 3:23

Pyke, 10 bytes


Try it here!

Or 9 bytes if null input isn't valid


Java 7, 69 bytes

 boolean c(String i){return i.matches("(?x)(?:a(?=a*(\\1?+b)))+\\1");}

Regex shamelessly 'borrowed' from here.

Full code & test cases:

Try it here (with all test cases).

class Main{
  static boolean c(String i){
    return i.matches("(?x)(?:a(?=a*(\\1?+b)))+\\1");

  public static void main(String[] a){




Ruby, 33 bytes

Try it online


Racket, 91 bytes

(λ(x)((λ(y)(equal?(append(make-list(- 1 y)#\a)(make-list y #\b))(cdr x)))(/(length x)2)))

Expects input in the form of a list of characters. If you really need to put it in as a raw string, that adds 21 extra characters (for 112 bytes):

(λ(x)((λ(y)(equal?(append(make-list(- 1 y)#\a)(make-list y #\b))(cdr(string->list x))))(/(string-length x)2)))

An even longer (102 bytes with list input) way, but I think it's creative so I'm leaving it here:

(λ(x)(and(eqv?(/(length x)2)(length(member #\b x)))(eqv?(length(remove-duplicates(member #\b x)))1)))

Explanation to follow.


Actually, 14 bytes


This uses the same strategy as xnor's solution for the first part: transform the input into a nested iterable.

Try it online!


"[]""ab"(t      translate "a" -> "[", "b" -> "]"
          ≡     eval (since this is evaluating a literal, it still works in the online interpreter) - leaves a list if the string is valid, else a string
           #    listify (does nothing to a list, makes a list of characters for a string)
            Æ   filter strings (take all string elements in the list - so an empty list if there are none)
             Y  boolean negate (an empty list is falsey and a non-empty list is truthy, so negation gets the correct value)

Ruby, 31 bytes

Aw, that poor syntax highlighter :)


Does s begin with one or more a? Is also that bunch of as ($&) the same as the rest of the string ($') if we replace all those as with bs?

test here


C#, 78 67 bytes

bool f(string s)=>Regex.IsMatch(s,"^(?'o'a)+(?'-o'b)+(?(o)(?!))$");

This implementation uses .NET Regex's "Balancing Group Definitions" to match the same number of 'a' and 'b' characters while ensuring that the input isn't an empty string by using the + quantifier.


Python, 101 bytes

def q(s):  
 for x in range(a):  
  if s[x]!='a' or s[a+x]!='b' or a*2!=len(s):a=0
return a

Not the most efficient, had some trouble with 0 being even. Could probably get it lower with python tricks.
Returns 0 if false, a positive integer if true. (which will be half len(s))


k (21 bytes)

Can probably be shorter



  • \$\begingroup\$ Gives the wrong answer for "abba" \$\endgroup\$ – geocar Jul 31 '16 at 13:02

PHP bounty version, 31 bytes

for PHP 4.1, call php-cgi -f <scriptname> s=<argument> (or in browser with ?s=<argument>)

for current PHP, use $_GET[s] instead of $s

31 bytes


unexpected ';' for valid, unexpected end of file or unexpected '}' for invalid


ok for valid, unexpected ';' or unexpected ']' for invalid

26 bytes

if empty input was undefined or valid:


29 bytes, if empty input was undefined or valid:


Abusing other control structures:

32 bytes


ok for valid, Parse error for invalid: unexpected ';', unexpected ']' or Cannot use [] for reading (for abab)

33 bytes

<?eval(strtr("1 or$s;",ab,'[]'));

same as 1|


ok for valid, unexpected end of file or unexpected '}' for invalid input

35 bytes:


infinite loop for valid (use for(;0;) to make finite), same as if for invalid

36 bytes


same as if

39 bytes


unexpected ';' for empty, same as if for other input


Matlab, 67 chars


The regular expression searches for exactly half the input's length in as consecutively at the beginning of the input string, followed by exactly half of the input's length in bs consecutively right up to the end of the input string. It returns [] on a non-even-length input, empty strings, and non-Language-L strings and only returns 1 on strings that are part of Language L.


Ruby, 42 bytes

This is a simple solution, but unfortunately longer than many of the other Ruby solutions.



def f(s)
  if s =~ /^a+b+$/ && s.count(?a) == s.count(?b)
    return true
    return nil

><>, 52 bytes

Prints zero if input is false, n otherwise (the number of a's and b's).


Try it online!


K, 21 Bytes

0b is false and 1b is true;

  • \$\begingroup\$ Edit - from seeing another answer I've shortened it down to 17 Bytes; {(~).(#:'=x)"ab"} \$\endgroup\$ – Chromozorz Jul 30 '16 at 22:44

Pyth, 7 bytes


Try it online

How it works

      SQ     sorted input
     _       reverse
   nV   Q    vectorized not-equal with input
  a      Q   append input
.A           test whether all elements are truthy

K, 10 bytes


Note this is a function, so it needs to be called:


= groups its arguments, so ="aaaaaabbbbbb" produces "ab"!(0 1 2 3 4 5;6 7 8 9 10 11) and ="aba" returns "ab"!(0 2;,1)

-':' is minus eachprior each. -': is a good way to find out if a series is increasing (or decreasing). -':'="aaaaaabbbbbb" gives us "ab"!(0 1 1 1 1 1;6 1 1 1 1 1) and -':'="aba" gives us "ab"!(0 2;,1)

1_' is one drop each which pops the first element off each list.

~/ is match over.


Perl 6, 49 bytes

grammar {token TOP{a<TOP>?b}}.parse(get).Bool.say

My entry for dmckee’s bounty. Checks the string using Perl 6’s parsing facilities.


Bash, 50 bytes

[[ $1 =~ a{$l}b{$l}$ ]]&&echo $[$l>0]

It always returns 1 in case the statement is true, otherwise it doesn't return something except if the input is the empty string '', then it returns 0.


$ bash script 'aa'
$ bash script 'ab'
$ bash script 'aabb'
$ bash script ''

It can be a bit shorter (46 bytes) if it returns $l in case of success.

[[ $1 =~ a{$l}b{$l}$ ]]&&echo $l 

In case of success it always returns a value > 0, if the input is the empty string it returns 0 and otherwise it doesn't return anything.


$ bash t.sh 'aa'
$ bash t.sh 'ab'
$ bash t.sh 'aabb'
$ bash t.sh ''

Thue, 39 bytes


Outputs a "1" for true and nothing for false.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy