В популярной (и обязательной) книге по информатике Питера Линца « Введение в формальные языки и автоматы » часто упоминается следующий формальный язык:

главным образом потому, что этот язык не может быть обработан с помощью конечных автоматов. Это выражение означает «Язык L состоит из всех строк« a », за которыми следуют« b », в которых число« a »и« b »равно и не равно нулю».

Вызов

Напишите работающую программу / функцию, которая получает строку, содержащую только «a» и «b» , в качестве входных данных и возвращает / выводит значение истинности , говоря, является ли эта строка допустимой для формального языка L.

• Ваша программа не может использовать какие-либо внешние вычислительные инструменты, включая сеть, внешние программы и т. Д. Оболочки являются исключением из этого правила; Bash, например, может использовать утилиты командной строки.

• Ваша программа должна возвращать / выводить результат «логическим» способом, например: возвращать 10 вместо 0, «звуковой сигнал», выводить на стандартный вывод и т. Д. Подробнее здесь.

• Применяются стандартные правила игры в гольф.

Это код-гольф . Самый короткий код в байтах побеждает. Удачи!

Правдивые тесты

"ab"
"aabb"
"aaabbb"
"aaaabbbb"
"aaaaabbbbb"
"aaaaaabbbbbb"

Ложные тесты

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

MATL , 5 4 байта

tSP-

Печатает непустой массив 1 с, если строка принадлежит L , и пустой массив или массив с 0 с (оба ложные) в противном случае.

Спасибо @LuisMendo за отыгрывание 1 байта!

Попробуйте онлайн!

Как это устроено

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.

Python 3, 32 байта

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

Выходы через код выхода : ошибка для false, нет ошибки для True.

Строка оценивается как код Python, заменяя символы « (за» aи « )за» b. Только выражения формы a^n b^nстановятся правильно сформированными выражениями, такими как скобки ((())), вычисляя их как кортеж ().

Любые несовпадающие парены дают ошибку, как и в случае нескольких групп (()()), так как разделителя нет. Пустая строка также терпит неудачу (это будет успешно exec).

Преобразования ( -> a, ) -> bосуществляется с помощью str.translate, которая заменяет символы , как показано на строку , которая служит в качестве таблицы преобразования. Учитывая строку длиной 100 ") (" * 50, таблицы отображают первые 100 значений ASCII как

... Z[\]^_`abc
... )()()()()(

которая принимает ( -> a, ) -> b. В Python 2 должны быть обеспечены преобразования для всех 256 значений ASCII, требующих на "ab"*128один байт больше; спасибо isaacg за указание на это.

Сетчатка , 12 байт

Кредиты FryAmTheEggman, который нашел это решение самостоятельно.

+`a;?b
;
^;$

Печать 1для правильного ввода и в 0противном случае.

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

объяснение

Балансирующие группы требуют дорогого синтаксиса, поэтому вместо этого я пытаюсь свести действительный ввод к простой форме.

Этап 1

+`a;?b
;

+Говорит Retina повторить этот этап в цикле , пока на выходе не перестает изменяться. Соответствует либо abили, a;bи заменяет его на ;. Давайте рассмотрим несколько случаев:

• Если as и bs в строке не сбалансированы таким же образом, как (и )обычно должно быть, некоторые aили bостанутся в строке, так как ba, или b;aне могут быть разрешены, и один aили сам bпо себе не может или. Чтобы избавиться от всех as и bs, должен быть один, соответствующий bправу каждого a.
• Если aи bне все вложенные (например, если у нас есть что-то вроде ababили aabaabbb), то в итоге мы получим несколько ;(и, возможно, несколько as и bs), потому что первая итерация найдет несколько abs, чтобы вставить их, и дальнейшие итерации сохранят количество ;в строке.

Следовательно, если и только если вход имеет форму , мы закончим с единственным в строке.anbn;

Этап 2:

^;$

Проверьте, содержит ли полученная строка только одну точку с запятой. (Когда я говорю «проверить», я на самом деле имею в виду «подсчитывать количество совпадений данного регулярного выражения, но поскольку это регулярное выражение может совпадать не более одного раза из-за привязок, это дает либо 0или 1.)

Haskell, 31 байт

f s=s==[c|c<-"ab",'a'<-s]&&s>""

Понимание списка [c|c<-"ab",'a'<-s]создает строку по одному 'a'для каждого 'a'входа s, а затем по одному 'b'для каждого 'a'входа s. Это позволяет избежать подсчета путем сопоставления с константой и создания выходных данных для каждого совпадения.

Эта строка проверяется, чтобы быть равной исходной строке, а исходная строка проверяется, чтобы быть непустой.

Грязь , 12 байт

A=\aA?\b
e`A

Попробуйте онлайн!

объяснение

Первая строка определяет нетерминал A, который соответствует одной букве a, возможно, нетерминалу A, а затем одной букве b. Вторая строка сопоставляет весь input ( e) с нетерминалом A.

8-байтовая неконкурентная версия

e`\a_?\b

После написания первой версии этого ответа я обновил Grime, чтобы он рассматривался _как имя выражения верхнего уровня. Это решение эквивалентно вышеупомянутому, но избегает повторения этикетки A.

Брахилог , 23 19 байт

@2L,?lye:"ab"rz:jaL

Попробуйте онлайн!

объяснение

@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

05AB1E , 9 байтов

Код:

.M{J¹ÔQ0r

Объяснение:

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

Последние два байта могут быть отброшены, если входные данные гарантированно не являются пустыми.

Использует кодировку CP-1252 . Попробуйте онлайн! ,

Желе , 6 байт

Ṣ=Ṛ¬Pȧ

Печатает саму строку, если она принадлежит L или пуста, и 0 в противном случае.

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это устроено

Ṣ=Ṛ¬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 == "".

Альтернативная версия, 4 байта (не конкурирующая)

ṢnṚȦ

Печать 1 или 0 . Попробуйте онлайн! или проверьте все контрольные примеры .

Как это устроено

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

J, 17 байт

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

Это работает правильно для предоставления фальси для пустой строки. Ошибка ложная.

Старые версии:

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

Доказательство и объяснение

Основным глаголом является вилка, состоящая из этих трех глаголов:

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

Это означает: «Меньшее из ( <.) length ( #) и результат правого зубца ( (-:'ab'#~-:@#))».

Правильный зуб - 4 поезда , состоящие из:

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

Позвольте kпредставить наш вклад. Тогда это эквивалентно:

k -: ('ab' #~ -:@#) k

-:является оператором совпадения, поэтому ведущие -:тесты на инвариантность под монадическим форком 'ab' #~ -:@#.

Поскольку левый зубец вилки является глаголом, он становится постоянной функцией. Итак, вилка эквивалентна:

'ab' #~ (-:@# k)

Правый зуб вилки ( -:) длина ( #) из k. Соблюдайте #:

   1 # 'ab'
'ab'
   2 # 'ab'
'aabb'
   3 # 'ab'
'aaabbb'
   'ab' #~ 3
'aaabbb'

Теперь, это kтолько на допустимых входных данных, поэтому мы сделали здесь. #ошибки для строк нечетной длины, которые никогда не удовлетворяют языку, поэтому мы также закончили.

В сочетании с меньшей длиной и этим, пустая строка, которая не является частью нашего языка, дает свою длину 0, и мы покончим с этим.

Бизон / YACC 60 (или 29) байтов

(Ну, компиляция для программы YACC - это пара шагов, поэтому может потребоваться включить некоторые для этого. Подробности см. Ниже.)

%%
l:c'\n';
c:'a''b'|'a'c'b';
%%
yylex(){return getchar();}

Функция должна быть достаточно очевидной, если вы знаете, как интерпретировать ее в терминах формальной грамматики. Синтаксический анализатор принимает любой abили aсопровождаемый любой приемлемой последовательностью, сопровождаемой a b.

Эта реализация опирается на компилятор, который принимает семантику K & R для потери нескольких символов.

Это более многословно, чем я хотел бы с необходимостью определить yylexи позвонить getchar.

Компилировать с

$ yacc equal.yacc
$ gcc -m64 --std=c89 y.tab.c -o equal -L/usr/local/opt/bison/lib/ -ly

(большинство опций для gcc относятся к моей системе и не должны учитываться в счетчиках байтов; возможно, вы захотите сосчитать, -std=c89что добавляет 8 к указанному значению).

Бежать с

$ echo "aabb" | ./equal

или эквивалент.

Значение истинности возвращается в ОС, а ошибки также передаются syntax errorв командную строку. Если я могу посчитать только ту часть кода, которая определяет функцию синтаксического анализа (то есть игнорировать вторую %%и все последующие), я получу счетчик в 29 байт.

Perl 5.10, 35 17 байт (с флагом -n )

say/^(a(?1)?b)$/

Гарантирует, что строка начинается с as, а затем повторяется на bs. Это соответствует только если обе длины равны.

Спасибо Мартину Эндеру за то, что он сократил вдвое число байтов и научил меня немного о рекурсии в регулярных выражениях: D

Возвращает всю строку, если она совпадает, и ничего, если нет.

Попробуй это здесь!

JavaScript, 54 55 44

s=>s&&s.match(`^a{${l=s.length/2}}b{${l}}$`)

Создает простое регулярное выражение на основе длины строки и проверяет ее. Для строки длиной 4 ( aabb) регулярное выражение выглядит так:^a{2}b{2}$

Возвращает истинное или ложное значение.

11 байт сэкономлено благодаря Нейлу.

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(''))

C 57 53 байта

t;x(char*s){t+=*s%2*2;return--t?*s&&x(s+1):*s*!1[s];}

Старое решение длиной 57 байт:

t;x(char*s){*s&1&&(t+=2);return--t?*s&&x(s+1):*s&&!1[s];}

Скомпилировано с gcc v. 4.8.2 @Ubuntu

Спасибо Угорен за советы!

Попробуйте это на Ideone!

Сетчатка , 22 байта

Другой короткий ответ на том же языке только что пришел ...

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

Попробуйте онлайн!

Это демонстрация балансирующих групп в регулярных выражениях, которая полностью объясняется Мартином Эндером .

Поскольку мое объяснение не приблизится к половине этого, я просто буду ссылаться на него и не буду пытаться объяснить, так как это нанесло бы ущерб славе его объяснения.

Befunge-93, 67 байт

0v@.<  0<@.!-$<  >0\v
+>~:0`!#^_:"a" -#^_$ 1
~+1_^#!-"b" _ ^#`0: <

Попробуй это здесь! Могу объяснить, как это работает позже. Могу также попытаться сыграть в гольф, чуть больше, просто для ударов.

MATL , 9 байт

vHI$e!d1=

Попробуйте онлайн!

Выходной массив верен, если он не пуст и все его записи отличны от нуля. В противном случае это ложь. Вот несколько примеров .

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

машинный код x86, 29 27 байт

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

Код сборки:

    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;

Итерирует aв начале байты, затем в следующих байтах 'b'. Первый цикл увеличивает счетчик, а второй цикл уменьшает его. Затем выполняет побитовое ИЛИ между следующими условиями:

1. Если в конце счетчик не равен 0, строка не совпадает
2. Если байт, следующий за последовательностью bs, не равен 0, строка также не совпадает

Затем он должен «инвертировать» значение истинности в eax- установить его в 0, если оно не было 0, и наоборот. Оказывается, самый короткий код для этого - следующий 5-байтовый код, который я украл из вывода моего компилятора C ++ 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

Рубин, 24 байта

eval(gets.tr'ab','[]')*1

(Это просто блестящая идея xnor в форме Ruby. Мой другой ответ - это решение, которое я сам придумал.)

Программа принимает входные данные , преобразует aи bк [и , ]соответственно, и оценивает его.

Допустимый ввод сформирует вложенный массив, и ничего не произойдет. Несбалансированное выражение приведет к сбою программы. В Ruby пустой ввод оценивается как nil, что приведет к сбою, потому nilчто не определил *метод.

Sed, 38 + 2 = 40 байт

s/.*/c&d/;:x;s/ca(.*)bd/c\1d/;tx;/cd/p

^{Непустая строка вывод правдоподобна}

Конечные автоматы не могут этого сделать, говорите? Как насчет конечных автоматов с петлями . :П

Запуск с rи nфлагами.

объяснение

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

JavaScript, 44 42

^{Вычеркнуто 44 все еще регулярно 44; (}

f=s=>(z=s.match`^a(.+)b$`)?f(z[1]):s=="ab"

Работает путем рекурсивного удаления внешнего aи bи рекурсивного использования внутреннего значения, выбранного, но .+. Если ^a.+b$слева не найдено совпадений , то окончательный результат заключается в том, является ли оставшаяся строка точным значением ab.

Тестовые случаи:

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)

ANTLR, 31 байт

grammar A;r:'ab'|'a'r'b'|r'\n';

Используется та же концепция, что и в ответе YACC @ dmckee , только чуть больше в гольфе.

Чтобы проверить, выполните шаги, описанные в руководстве по началу работы ANTLR . Затем поместите приведенный выше код в файл с именем A.g4и выполните следующие команды:

$ antlr A.g4
$ javac A*.java

Затем проверьте, введя STDIN grun A rтак:

$ echo "aaabbb" | grun A r

Если ввод действителен, ничего не будет выведено; если он является недействительным, grunвыдаст сообщение об ошибке (или token recognition error, extraneous input, mismatched inputили no viable alternative).

Пример использования:

$ echo "aabb" | grun A r
$ echo "abbb" | grun A r
line 1:2 mismatched input 'b' expecting {<EOF>, '
'}

C 69 байтов

69 байт:

#define f(s)strlen(s)==2*strcspn(s,"b")&strrchr(s,97)+1==strchr(s,98)

Для незнакомых:

• strlen определяет длину строки
• strcspn возвращает первый индекс в строке, где найдена другая строка
• strchr возвращает указатель на первое вхождение символа
• strrchr возвращает указатель на последнее вхождение символа

Большое спасибо Титу!

R, 64 61 55 байтов, 73 67 байтов (устойчивый) или 46 байтов (если разрешены пустые строки)

1. Опять же, ответ кснора переработан. Если по правилам подразумевается, что входные данные будут состоять из строки as и bs, он должен работать: возвращает NULL, если выражение допустимо, throws и error или ничего другого.

   if((y<-scan(,''))>'')eval(parse(t=chartr('ab','{}',y)))
   

2. Если входные данные не устойчивы и могут содержать некоторый мусор, например aa3bb, следует рассмотреть следующую версию (должна возвращаться TRUEдля истинных тестовых случаев, а не NULL):

   if(length(y<-scan(,'')))is.null(eval(parse(t=chartr("ab","{}",y))))
   

3. Наконец, если разрешены пустые строки, мы можем игнорировать условие для непустого ввода:

   eval(parse(text=chartr("ab","{}",scan(,''))))
   

   Опять NULL, если успех, все остальное иначе.

Japt , 11 байт

©¬n eȦUg~Y

Попробуйте онлайн!

Дает или trueили false, за исключением того, что ""дает ""ложь в JS.

Распаковано и как это работает

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

Принято из решения MATL Денниса .

C (Ansi), 65 75 байт

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;}

Объяснение:

Устанавливает значение j и увеличивает j на каждом b и уменьшает j на любом другом. Проверяется, если буква перед меньше или равна следующей букве, чтобы предотвратить работу abab

Правки

Добавлены проверки для abab случаев.

Пакет, 133 байта

@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

Возвращает ERRORLEVEL0 при успехе, 1 при ошибке. Пакетный режим не любит заменять подстроки на пустых строках, поэтому мы должны проверить это заранее; если бы пустой параметр был допустимым, строка 6 не была бы необходима.

PowerShell v2 +, 61 52 байта

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

Принимает ввод $nв виде строки, создает $xкак half the length. Создает -andбулево сравнение между $nи -matchоператором регулярного выражения с регулярным выражением равного числа a's и b' s. Выходы логические $TRUEили $FALSE. Это $n-andтам для учета ""= $FALSE.

Альтернативный, 35 байт

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

При этом используется регулярное выражение из ответа Лики , основанное на балансирующих группах .NET, только что инкапсулированное в -matchоператоре PowerShell . Возвращает строку для truey или пустую строку для falsey.

Pyth - 13 байт

&zqzS*/lz2"ab

Разъяснение:

  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

Haskell, 39 байт

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

Пример использования: p "aabb"-> True.

scanl(\s _->'a':s++"b")"ab"xпостроить список всех ["ab", "aabb", "aaabbb", ...]с общим количеством (length x)элементов. elemпроверяет, есть ли xв этом списке.

Python, 43 40 байт

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

рассмотрел очевидное решение благодаря Leaky Nun

другая идея, 45 байт:

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

-4 байта с помощью len / 2 (я получаю ошибку, когда половина приходит последней)

теперь дает false для пустой строки

-3 байта благодаря xnor