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:

$$\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 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"

Leaderboard

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 ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 48934; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

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

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

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

var OVERRIDE_REG = /^Override\s*header:\s*/i;

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

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      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],
        link: a.share_link,
      });
    
  });
  
  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;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    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)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}

body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

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

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

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

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

Answer 1

Matlab, 67 chars

s=input('');l=num2str(length(s)/2);regexp(s,['^a{',l,'}b{',l,'}$'])

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.

Answer 2

TI-Basic, 35 bytes

Zero is True; anything else is False.

Input Str1
1+.5length(Str1
inString(Str1,"a",Ans) or Ans≠inString(Str1,"b

Explanation

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

Answer 3

Ruby, 42 bytes

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

->s{s=~/^a+b+$/&&s.count(?a)==s.count(?b)}

Ungolfed:

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

Answer 4

><>, 52 bytes

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

0&i:0(?v10.
&v?(2l~<0rv!?='a'r0!?='b'&+1
 >l0=&*n;n<

Try it online!

Answer 5

K, 21 Bytes

0b is false and 1b is true;

    f:{(~).{+/x=y}[x]'"ab"}
    tests:("ab";"abbbb";"bbbbaa";"aabbababba";"bb";"aabaaabaaa";"aabbb";"aaabbaaabb";"ba";"bbbabbaabb")
    f'tests
    1001000010b

Answer 6

K, 10 bytes

~/1_'-':'=

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

  ~/1_'-':'="aaaaaabbbbbb"
1
  ~/1_'-':'="aba"
0

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

Answer 7

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.

Answer 8

Bash, 50 bytes

l=$[${#1}/2]
[[ $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.

Example:

$ bash script 'aa'
$ bash script 'ab'
1
$ bash script 'aabb'
1
$ bash script ''
0

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

l=$[${#1}/2]
[[ $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.

Examples:

$ bash t.sh 'aa'
$ bash t.sh 'ab'
1
$ bash t.sh 'aabb'
2
$ bash t.sh ''
0

Answer 9

Thue, 39 bytes

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

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

Answer 10

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.

Answer 11

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

Answer 12

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

Answer 13

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$r`b")})

Answer 14

Perl 6, 25 bytes

{$_&&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.

Answer 15

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

Answer 16

///, 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!

Answer 17

Keg, 14 bytes

:⑴½ℤ:a⅍*$b⅍*+=

Try it online!

Same approach as the stax answer.

Answer 18

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.

Answer 19

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

Answer 20

Clojure, 88 bytes

(defn a[s](let[g(re-find #"^(a+)(b+)$"s)](and(not(nil? g))(=(count(g 1))(count(g 2))))))

Ungolfed version:

(defn ab?[s]
  (let [ groups  (re-find #"^(a+)(b+)$" s) ]
    (and (not (nil? groups))
         (= (count (groups 1)) (count (groups 2))))))

Try it online!

Answer 21

J, 11 bytes

=/@(+/"1@=)

Try it online!

Answer 22

Vyxal, 7 bytes

fCḂ$sεg

Try it Online!

Answer 23

sed, 23 bytes

:0
s/a1*b/1/
t0
/^1$/!d

Try it online!

Repeatedly replace the anything of the form a1*b with 1, then check if the output contains a single 1.

Answer 24

Lua, 46 bytes

a,b=(...):match"^(a+)(b+)$";return a and#a==#b

Try it online!

Answer 25

BQN, 12 10 bytes

(¬≡∨)-⟜⊑⎊≢

Anonymous tacit function; takes a string and returns 0 for falsey, 1 for truthy. Try it here!

Explanation

(¬≡∨)-⟜⊑⎊≢
        ⊑     Get the first character of the string
     -⟜       Subtract it from each character of the string
               (where 'a'-'a' is 0, 'b'-'a' is 1, etc.)
         ⎊    If that errored because the string is empty,
          ≢   use the string's shape instead: an array containing a single 0
(   )         Apply this function to that list of 0's and 1's:
   ∨           Sort in descending order
  ≡            Is the result identical to
 ¬             logically negating each?
               If so, we have some number of 0's followed by an equal number of 1's

Answer 26

APL, 20 bytes

{⍵≡∊'ab'⍴⍨¨1⌈⌊2÷⍨≢⍵}

Naive approach: build the correct string of the same length, then compare.

Answer 27

Julia, 33 bytes

^ =count
!s='a'^s=='b'^s>"ba"^s<1

Attempt This Online!

The dyadic operator ^ is assigned to count, so count(x,y) becomes x^y. Alternatively, the operator ~ wouldn't require a space in the assignment statement due to its low precedence. In fact, ~ is evaluated after comparisons, making it a poor choice for this solution, which relies on multiple comparisons to ensure that the input has:

• an equal (non-zero) number of 'a' and 'b', and
• no occurrence of "ba".

Answer 28

Knight (v2), 23 bytes

O&=l/L=xP2?x+*"a"l*"b"l

Try it online!

OUTPUT(                        # Output...
    &                          #   the first value...
    : = half_len               #     which is assigning the value of 
      : /                      #       the floored quotient of
        : LENGTH(              #         - the length of
          : = str PROMPT()     #           - the line from stdin, assigned to str
          )
         : 2                   #         - and 2
                               #   ... if it is falsy, or...
    : ?                        #     whether the following values are equal:
      : str                    #       - str
      : +                      #       - concatenated:
        : * "a" half_len       #         - "a" repeated half_len times
        : * "b" half_len       #         - "b" repeated half_len times
)

It is the simple approach for languages with string multiplication, which first tests the length, then compares it to "a" * len(str) // 2 + "b" * len(str) // 2.

The code will output either true for true, or either 0 or false for false.

Answer 29

TypeScript’s type system, 80 bytes

type F<S>=S extends`a${infer A}b${infer B}`?B extends`a${any}`?B:F<`${A}${B}`>:S

Try it at the TS playground! Returns falsey (empty string) if there is an equal number of As and Bs, non-empty string otherwise.

This is a generic type F<S> which takes a string type and recursively removes a leading a and the first b, unless there’s an a after the first b.

This is the kind of challenge where TS types can really be competitive with actual programming languages!

Answer 30

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.