Пара задач по теории алгоритмов (прим. рек-я, конечн. авт-т)

[DustBit]

Всем привет, помогите, пожалуйста, справиться с этими задачами:

1) Показать, что если f(x,y) - примитивно рекурсивна, то и f(y,x) - тоже.

2) Пусть L - язык, состоящий из бесскобочных алгебраических выражений над именами переменных с операциями сложения и умножения (идентификаторы для имён - слова в латинице). Показать, что L является автоматным. Построить конечный автомат и регулярное выражение, определяющие этот язык.


В первой, видимо, надо плясать от определения, раз ничего не дано, а есть абстрактная функция. Но вот не знаю, откуда начать. Может, попробовать от противного и показать, что f(y,x) - не рекурсивна?..

А во второй я вообще хз чо делать, буду рад, если кто поможет расшифровать условие хотя бы)

[Xaositect]

1. Постройте $f(y, x)$ как композицию $f(x, y)$ и каких-нибудь еще примитивно-рекурсивных функций.