90
\$\begingroup\$

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"

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>

\$\endgroup\$
18
  • 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\$ Jul 20, 2016 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, 2016 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, 2016 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, 2016 at 13:27
  • 2
    \$\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\$ Jul 22, 2016 at 22:47

108 Answers 108

1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\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, 2016 at 16:38
  • \$\begingroup\$ You're not using TI-Basic's notion of truthy/falsy here. How is that allowed? \$\endgroup\$
    – Jakob
    Aug 29, 2017 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, 2017 at 23:08
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Edit - from seeing another answer I've shortened it down to 17 Bytes; {(~).(#:'=x)"ab"} \$\endgroup\$
    – Chromozorz
    Jul 30, 2016 at 22:44
1
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Thue, 39 bytes

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

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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")})
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Keg, 14 bytes

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

Try it online!

Same approach as the stax answer.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.)
\$\endgroup\$
0
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

J, 11 bytes

=/@(+/"1@=)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 7 bytes

fCḂ$sεg

Try it Online!

\$\endgroup\$
2
  • \$\begingroup\$ I got it down to 6 bytes. \$\endgroup\$
    – Deadcode
    Jul 7, 2022 at 21:41
  • 1
    \$\begingroup\$ (Actually, 4 bytes if taking a list of characters as input, 5 bytes if taking a string as input.) \$\endgroup\$
    – Deadcode
    Jul 9, 2022 at 15:34
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

APL, 20 bytes

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

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

\$\endgroup\$
1
  • \$\begingroup\$ Welcome to CGCC! Your answer can be more interesting to others if you comment on how you came up with it. Also, make sure to take our tour and earn a badge. \$\endgroup\$ Jul 11, 2022 at 6:50
1
\$\begingroup\$

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".
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.