# 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:

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

# Thue, 39 bytes

$::=::: ab::=x axb::=x -x-::=~1 ::= -$-


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

# R, 79 bytes

a=function(s){all(nchar(strsplit(s,"ab")[[1]])==nchar(s)/2-1)&&!grepl("ba",s)}


Tests if when split on "ab" all substrings are the same precalculated length, and it tests if the pattern "ba" occurs anywhere.

## awk, 53 bytes

Solution forms pairs from the assumed beginning of as (i) and bs ((NF+1)/2)and iterates towards a's ending. Truth value is kept in a anding it with result of comparing the current pair ($i$(i+j)) to ab.

{for(a=j=++NF/2;++i<=j;)t=t&&($i$(i+j)=="ab");exit t}


Run it:

$echo abab|awk -F '' '{for(a=j=++NF/2;++i<=j;)t=t&&($i$(i+j)=="ab");exit t}'$ echo $? 0$ echo aabb|awk -F '' '{for(a=j=++NF/2;++i<=j;)t=t&&($i$(i+j)=="ab");exit t}'
$echo$?
1


# SmileBASIC 3, 38 bytes

INPUT V$L=LEN(V$)/2?"a"*L+"b"*L==V$&&L  For all integers n > 2 there is only one valid string in this language. So we build that string, given the length of the input, and check if it equals the input. Prints 0 if false, 1 if true (SB truthiness convention.) INPUT V$     'read line from console, store in V$L=LEN(V$)/2  'number of As/Bs in valid string (length of input / 2)

?                    'print
"a"*L+"b"*L         'valid A/B string for given length
==       'equals
V$'input && 'and L 'length is non-zero  # Prolog (SWI), 34 33 bytes -[]. -L:-append([97|M],b,L),-M.  Try it online! # PowerShell, 39 bytes $args-in($args|% t*y|%{($r="a$r"+'b')})  Try it online! # PowerShell 5.1, 37 bytes $args-in($args|% t*y|%{($r="a$rb")})  # Ruby, 17 bytes (16 + '-n' flag) p~/^(a\g<1>?b)$/


Try it online!

The recursive regex solution ported to ruby.

{$_&&try !TR/ab/()/.EVAL}  Try it online! Port of xnor's answer that returns True and Nil or an empty string. This translates all abs to the characters () and EVALs it. If there are unmatched parenthesises like aaab or ba, it errors. If there are two pairs of ab in a row, that errors as ()() is attempting a function call on an empty list. Otherwise, it returns an empty list (), which we then Boolean not (!) to get a truthy value. The try swallows the errors and returns Nil instead. If the input is empty, then it returns the empty string. # Burlesque, 21 bytes Jsojgwsa2==j)-]sm&&&&  Try it online! Jso #(Non-destructive) is sorted? jgw #Group like elements, prepend with length of group sa2== #2 distinct elements j)-] #Take the lengths sm #Are the same &&&& #All are true  # ///, 13 bytes /$a///$b//$


Input is hard-coded at the end of the program since Slashes doesn't have input. Outputs only "$" for a truthy value and something else otherwise. Try it online! # 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)  # SNOBOL4 (CSNOBOL4), 81 78 bytes  INPUT POS(0) SPAN('A') @X REM . Y :F(END) OUTPUT =IDENT(Y,DUPL('B',X)) 1 END  Try it online! Match 'A's starting at beginning of string and set length to X. If the REMainder of the string is the same as X 'B's then output 1 else output nothing. ## NST, 6 bytes You need to enclose the input in brackets, e.g. ["ab"]. ab"Ṅ*§  ## Explanation "ab" Define the string "ab". Ṅ* Multiply this string by the natural number set. The natural number set is [1, 2, 3, 4, 5, ...] Since in NST a string is technically a set, this yields the output ["ab", "aabb", "aaabbb", ...] instead. § Does the (implicit) input belong to this set? (Implicit input goes ahead of the operand.)  ## Clojure, 52 bytes #(=(seq %)(mapcat(fn[c](repeat(/(count %)2)c))"ab"))  Instead of parsing the string this one generates a sequence how it should look like :) (seq "") is nil but the mapcat produces an empty list, so (f "") is false. # ///, 41 bytes + input [47 with empty input acceptance] /'/"|//|a/a|//a|b/|//"|"///a///b///"|//'(input)' A B C D E F G NB: second line is used in explanation, not part of the code There's no /// submission yet?! Outputs | for true, (empty output) for false. Gives a false positive on the empty input, add /''/|/ at the start for +6 bytes if needed. Example parsings (which hopefully should be illustrative): • 'aabb' A "|aabb"| B "a|abb"| B "aa|bb"| C "a|b"| C "|"| D | • 'abab' A "|abab"| B "a|bab"| C "|ab"| E "|b"| F "|"| G "| G Try it online! # Lua, 37 bytes Works with Lua 5.1, Lua 5.2, and Lua 5.3. os.exit((...):match"^%bab$":find"ba")


Try it online!

Exit status zero for truthy, non-zero for falsey. (Assumes the default success exit code is zero.)

The match call uses %b to check if the string is a "balanced" (in the sense of parentheses) string of a and b. In particular, this means the numbers of a and b is the same and the string is non-empty. If this fails, it will return nil, and the call to find will throw, giving a falsey exit status. Otherwise, it will return the whole string again.

If the call to find fails, then all the a preceed all the b and the string is valid. find will return nil and os.exit will give a default exit status (zero). If the call to find succeeds, it will return the index where it found ba which will be nonzero.

# ///, 38 + input bytes

input goes between the n and the x at the end.

/nx///ba/0//ab///a/0//b/0//n0/0//x//nx


A lot of this code is getting the output format correct. Outputs a single n if it it truthy, and a string consisting of 0s if it it falsy.

# ///, 11 + input bytes

/ba/0//ab//


Input goes at the end. Output the empty string if it is falsy, or a string consisting of a, b, and 0 if it is truthy.

# Batch, 50 bytes

@set x=%1
@if %x:b=%%x%%x:a=% neq %x:b=a%%x:a=b% *


Output nothing and return 0 for true and something returning 9009 for false

If %x% contain a as and b bs, %x:b=%%x%%x:a=% contains 2a as and 2b bs, while %x:b=a%%x:a=b% contain a+b as and a+b bs, so if they're equal, a=b. Meanwhile, %x% in %x:b=%%x%%x:a=% occupies the middle part, which in %x:b=a%%x:a=b% is a as and a bs, so they can be and will be equal if it matchs {a}^n{b}^n.

For empty string, the IF statement fails to parse and echo about that.

## Python 2.7, 37 bytes

lambda s:s.count('a')==s.count('b')>0


# Gol><>, 26 bytes

&TiE!tlF:a=Q&P&~{|}|l&-zh


Wow, five minutes and it is already smaller, 4 bytes knocked off!

Try it online!

Older version, 30 bytes

&TiE!tlF:a=:Q&P&~|zQ}||l&-0=h


Wow! This was going to be alot larger than this, but I realized that I can combine 2 checks in one towards the end. This can be golfed alot more, but I will be working on that soon!!!

&TiE!t                           //Get all of the characters
lF                         //Loop through the entire stack
:a=:                    //Check if it is equal to a
Q&P&~|              //If so, increment a variable and delete that character
zQ}|          //Otherwise, continue
|         //end of loop
l&-0=h   //the remaining b# is subtracted from the # of a, if it is zero it will output 1, otherwise 0


Try it online!

• abab should be falsey. I know the title is misleading, but truthy cases are only as followed by only bs. e.g. aaabbb is true, ababab is false – Jo King Mar 20 '19 at 23:41
• @JoKing Well then, I will fix that, it should be an easy fix where I do the deleting process, delete the previous letter rather than itself, and then check if the previous and itself are the same. Thanks for pointing that out, I'll fix it as soon as I have time – KrystosTheOverlord Mar 21 '19 at 0:12

# Perl 6 (33 bytes)

{?/^(a+)(b+)$/&&$0.ords==\$1.ords}

• Fixed the first problem. And I'm sure chrs works, because == coerces its arguments into numbers before performing the comparison. – bb94 Mar 21 '19 at 2:07
• You're right; I was thinking of ords. – bb94 Mar 21 '19 at 2:13
• 30 bytes – Jo King Mar 21 '19 at 2:22

# APL(NARS), 23 chars, 46 bytes

{⍵≡'':0⋄⍵≡'ab'/⍨⌈2÷⍨≢⍵}


test:

  f←{⍵≡'':0⋄⍵≡'ab'/⍨⌈2÷⍨≢⍵}
f ''
0
f¨(,'a')(,'b')('aa')('ba')
0 0 0 0
f¨('ab')('aabb')('aaabbb')('aaaabbbb')
1 1 1 1
f¨('abb')('aabbb')('aaaabbb')('aaaaabbbb')
0 0 0 0


# C# (Visual C# Interactive Compiler), 54 bytes

x=>x!=""&!x.OrderBy(y=>-y).Where((y,i)=>y==x[i]).Any()


Try it online!

Port of Dennis's MATL solution. Below is a 48 byte version that matches the empty string.

x=>!x.OrderBy(y=>-y).Where((y,i)=>y==x[i]).Any()


Try it online!

# Python 2, 42 bytes

f=lambda s:s=='ab'or s<s[-1:]>0<f(s[1:-1])


Try it online!

# Stax, 8 bytes

é«<òαøòâ


Run and debug it

It compares the input with "ab" having its characters repeated inputLength / 2 times.

# C, 85 bytes

n,d;f(char*v){while(*v)if(*v++&1){if(n++,d)return 0;}else d?n--:(n--,d=1);return!n;}


Pretty long. Seems to handle all edge cases correctly.

Ungolfed:

n, d;
f (char *v) {
while (*v)
if (*v++ & 1) {
if(n++, d)
return 0;
} else
d ? n-- : (n-- , d = 1);
return !n;
}


# brainfuck and bfasm, 995 and 119 bytes

Quite easy to outgolf.

Generated using following assembly code:

mov r4,.a
lbl 1
in_ r1
jz_ r1,3
eq_ r1,r4
jnz r1,2
inc r3
dec r2
lbl 2
inc r2
jmp 1
lbl 3
eq_ r2,r3
out r2


And then optimized by hand.

+>+[<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>>--[----->+<]>-----<<<<<]>+<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>,>>>>+++<<<<<<+>>[<<[-]<+>>>-]<<<[>>>+<<<-]>[<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>[-]]>>>>>>[-]<<<<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>[<<+>>-]+>>>[<<<<<-<+>>>>>>-]<<<<<<[>>>>>>+<<<<<<-]>[>>-<<[-]]>>>>>>++<<<<[<<<+>+>>-]<<<[>>>+<<<-]>[<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>[-]]>>>>>>[-]<<<<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>>+<-<<<]>++<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]>>[-]<<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>+>>>+<<<<<<<<<[-]>[-]>>>>>>>>[<<<<<<<<+>+>>>>>>>-]<<<<<<<[>>>>>>>+<<<<<<<-]>>>>>>>[-]<<<<<<]>+++<<+<<[>>->+<<<-]>>>[<<<+>>>-]<[->+<<[>>>-<<+<-]>[<+>-]>>[<->[-]]<[<<<+>>>-]<]>>[-]<<<<[>>+>+<<<-]>>[<<+>>-]>[[-]>>>[<<<+>>>-]+>[<<<<-<+>>>>>-]<<<<<[>>>>>+<<<<<-]>[>>>-<<<[-]]>>>.<<<]<<<[>>+>+<<<-]>>[<<+>>-]>[[-]<<<[-]>[-]>>]<<]


Try it online!

# C# .NET 135 bytes

public class P{public static void Main(string[]a){System.Console.Write(a[0]!=""&&a[0].Split('a').Length-1==a[0].Split('b').Length-1);}}


Try online

# GolfScript, 20 bytes

.,2//zip{"ab"=}%{&}*


Try it online!

## Unix TMG, 64 bytes

p:<a>f((<b>))parse((any(!<<>>)|={<1>}));f:proc(x)<a>f((<b>x))|x;


Works by recursive-descent parsing. It outputs "1" for match, nothing otherwise.

Expanded:

prog:   <a> recurs(( <b> )) parse(( any(!<<>>) | = { <1> } ));
recurs: proc(x) <a> recurs(( <b> x ))
| x;


The solution is based on the one in McIlroy's Tmg Manual (1972) for anbncn.