5
$\begingroup$

In Chomskhy classification of formal languages, I need some examples of Non-Linear, Unambiguous and also Non-Deterministic Context-Free-Language(N-CFL)?

  1. Linear Language: For which Linear grammar is possible $( \subseteq CFG)$ e.g.
    $ L_{1} = \{a^nb^n | n \geq 0 \} $

  2. Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
    $ L_{2} = \{a^nb^nc^m | n \geq 0, m \geq 0 \} $
    $L_{2}$is also a Non-Linear CFG (and unambiguous).

  3. Non-Deterministic Context Free Language(N-CFG): only Non-Deterministic Push-Down-Automata(N-PDA) is possible e.g.
    $ L_{3} = \{ww^{R} | w \in \{a, b\}^{*} \} $
    $L_{3}$ is also Linear CFG

4. Ambiguous CFL: CFL for which only ambiguous CFG is possible $ L_{4} = \{a^nb^nc^m | n \geq 0, m \geq 0 \} \bigcup \{a^nb^mc^m | n \geq 0, m \geq 0 \} $
$L_{4}$ is both non-linear and Ambiguous CFG And Every $ Ambigous CFL \subseteq NCFL$.

My Question is:

Whether all non-linear, Non-Deterministic CFL are Ambiguous?  

If not then I need a example that is non-linear, non-deterministic CFL and also unambiguous?


Venn-diagram for Chomsky classification of formal languages.

enter image description here


  • 0
    @Tara: You're right. I posted an answer then.2012-11-27

1 Answers 1

3

Let $L$ be the language of well-formed expressions using a single type of brackets such as (()(()())). This language is nonlinear, deterministic and unambiguous.

Let $R$ be the language $\{w w^R\}$ of even palindromes. It is unambiguous, linear but nondeterministic.

Assume that alphabets of $L$ and $R$ are disjoint. Then $L \cup R$ is unambiguous, nonlinear (due to $L$), and nondeterministic (due to $R$).

  • 1
    you were correct there is also [linear ambiguous language](http://math.stackexchange.com/questions/252454/in-context-of-chomskhy-classification-of-formal-languages?answertab=oldest#tab-top) thanks!2012-12-19