Énoncé
EX 1
1.
2.
3.
Palindromes :
Non-palindromes :
4.
Non-square words :
But it a bit impractical, let’s rather note that:
is of the form:
EX 2
where
It can be shown by induction on the length of the run that for all
Donc
EX 3
Method 1:
Out of each state of , is appended to the stack, and one reads the content of the stack through an automaton that reckons .
Method 2:
The aim is to ensure the following property :
with in
and it is accepted when
(to have )
Leave a comment