Машина Тьюринга.

[LeoRed]

A={(,)}. Определить, сбалансировано ли слово Р по круглым скобкам.

[min@y™]

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

[Slym]

program Balance;
var
  i,c:Integer;
  s:string;
begin
  c:=0;
  s:='{((,)}';
  for i:=1 to Length(s) do
    if s[i]='(' then Inc(c) else if s[i]=')' then Dec(c);
  if c=0 then Writeln('balanced') else Writeln('not balanced');
end.

но это нифига не тьюринга

[rrrFer]

в состоянии 1:
 - считал ) - значит не сбаллансированно
 - считал ( - удаляешь символ, переходишь в состояние 2
 - пустая лента - сталансировано.
в состоянии 2:
  - считал ( - переходишь вправо
  - считал ) - удаляешь символ переходишь в состояние 3
в состоянии 3:
  - если не первый символ ленты - идешь влево
  - иначе переходишь в состояние 1

Ну это схематично.