0
$\begingroup$

This is very much clear to me that an FSM has limited memory (sufficient to store present state). How do I prove that (intutively or otherwise) that a CFL has more memory than a DFA or NFA (thus making a CFL more powerful than FA) ?

$\endgroup$
  • $\begingroup$ Languages don't have memory per se (see also this reference question). What are you really asking? If your question is "How do I show that a language can not be accepted by an NFA?", then we've got you covered. $\endgroup$ – Raphael Sep 9 '13 at 12:42
1
$\begingroup$

There's a small mistake in your question.

The FSM (DFA or NFA) are machines that accept regular languages.

the CFL is also a language.

They are accepted by a machine called PDA (PushDown Automata) which you can think of as a generalization of the a DFA/NFA.

A PDA is like a NFA but in addition, it also has a stack. So it can accept (context free) languages like $L = \{0^p1^p | p \geq 0\}$

Its fairly easy to show that the PDA is more powerful than DFA.. (see it accepts $L$ that the DFA cannot)

We will show something stronger, i.e. formally define the construction of the PDA that will show that any language accepted by some DFA is also accepted by some PDA .

a PDA is 6 tuple $(Q, \Sigma, \Gamma, \delta, q_0, F )$, where,

  • $Q$ is the set of states
  • $\Sigma$ is the input alphabet,
  • $\Gamma$ is the stack alphabet,
  • $\delta$ is the transition func. $\delta:(Q \times \Sigma_\epsilon \times \Gamma_\epsilon) \rightarrow \mathcal{P}(Q\times \Gamma_\epsilon)$ ,
  • $q_0 \in Q$,
  • $F \subseteq Q$

now observe that a DFA/NFA is just the same thing where $\Gamma$ is always 'empty'.

$\endgroup$
  • $\begingroup$ How much stack is available in PDA? $\endgroup$ – gpuguy Sep 9 '13 at 9:58
  • $\begingroup$ the size of the stack is unbounded $\endgroup$ – Subhayan Sep 9 '13 at 10:00
  • $\begingroup$ ok, got it. but asking just out of curiosity how is this practical when it has infinite memory? $\endgroup$ – gpuguy Sep 9 '13 at 10:02
  • 1
    $\begingroup$ i am not really sure, but the answer i generally give is "you are in the realms of theory ! practice confines you, theory can set you free :) " $\endgroup$ – Subhayan Sep 9 '13 at 10:06
  • 2
    $\begingroup$ @gpuguy: It is not practical. In practice, if the universe contains only a finite amount of information storage capacity, then every machine we can build is finite-state. In the absence of theories of physics that allow for unbounded information, the main reason to use machine models beyond DFA/NFA is that they are more expressive. $\endgroup$ – András Salamon Sep 9 '13 at 10:30

Not the answer you're looking for? Browse other questions tagged or ask your own question.