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

Question

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

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

Answer 1

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.

Answer 2

Python 3, 32 bytes

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

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.

Answer 3

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

Answer 4

Haskell, 31 bytes

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.

Answer 5

Grime, 12 bytes

A=\aA?\b
e`A

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.

Answer 6

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

Answer 7

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

Answer 8

Jelly, 6 bytes

Ṣ=Ṛ¬Pȧ

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

Try it online! or verify all test cases.

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.

Answer 9

J, 17 bytes

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

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

Old versions:

-:'ab'#~-:@#
2&#-:'ab'#~#   NB. thanks to miles

Proof and explanation

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.

Answer 10

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.

Answer 11

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!

Answer 12

JavaScript, 54 55 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(''))

Answer 13

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!

Answer 14

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.

Answer 15

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.

Answer 16

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

Answer 17

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

Answer 18

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.

Answer 19

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

Answer 20

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)

Answer 21

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>, '
'}

Answer 22

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!

Answer 23

R, 64 61 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.

Answer 24

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

Adopted from Dennis' MATL solution.

Answer 25

C (Ansi), 65 75 Bytes

Golfed:

l(b,i,j,k)char*b;{for(i=j=0;(k=b[i++])>0&k<=b[i];)j+=2*(k>97)-1;return !j;}

Explanation:

Sets a value j and increments j on each b and decrements j on anything else. Checked if the letter before is less than or equal the next letter so prevent abab from working

Edits

Added checks for abab cases.

Answer 26

Batch, 133 bytes

@if ""=="%1" exit/b1        Fail if the input is empty
@set a=%1                   Grab the input into a variable for processing
@set b=%a:ab=%              Remove all `ab` substrings
@if "%a%"=="%b%" exit/b1    Fail if we didn't remove anything
@if not %a%==a%b%b exit/b1  Fail if we removed more than one `ab`
@if ""=="%b%" exit/b0       Success if there's nothing left to check
@%0 %b%                     Rinse and repeat

Returns an ERRORLEVEL of 0 on success, 1 on failure. Batch doesn't like to do substring replacement on empty strings, so we have to check that up front; if an empty parameter was legal, line 6 wouldn't be necessary.

Answer 27

PowerShell v2+, 61 52 bytes

param($n)$x=$n.length/2;$n-and$n-match"^a{$x}b{$x}$"

Takes input $n as a string, creates $x as half the length. Constructions an -and Boolean comparison between $n and a -match regex operator against the regex of an equal number of a's and b's. Outputs Boolean $TRUE or $FALSE. The $n-and is there to account for ""=$FALSE.

Alternate, 35 bytes

$args-match'^(a)+(?<-1>b)+(?(1)c)$'

This uses the regex from Leaky's answer, based on .NET balancing groups, just encapsulated in the PowerShell -match operator. Returns the string for truthy, or empty string for falsey.

Answer 28

Pyth - 13 bytes

&zqzS*/lz2"ab

Explained:

  qz          #is input equal to
          "ab #the string "ab"
     *        #multiplied by
      /lz2    #length of input / 2
    S         #and sorted?
&z            #(implicitly) print if the above is true and z is not empty

Answer 29

Haskell, 39 bytes

p x=elem x$scanl(\s _->'a':s++"b")"ab"x

Usage example: p "aabb" -> True.

scanl(\s _->'a':s++"b")"ab"x build a list of all ["ab", "aabb", "aaabbb", ...] with a total of (length x) elements. elem checks if x is in this list.

Answer 30

Python, 43 40 Bytes

lambda s:''<s==len(s)/2*"a"+len(s)/2*"b"

connsidered the obvious solution thanks to Leaky Nun

other idea, 45 bytes:

lambda s:s and list(s)==sorted(len(s)/2*"ab")

-4 bytes by using len/2 (i get an error when the half comes last)

now gives false for the empty string

-3 bytes thanks to xnor