Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
587 views
in Technique[技术] by (71.8m points)

finite automata - Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?

In the Chomsky 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( ? CFG) e.g.
    L1 = {anbn | n ≥ 0 }

  2. Deterministic Context Free Language(D-CFG): For which Deterministic Push-Down-Automata(D-PDA) is possible e.g.
    L2 = {anbncm | n ≥ 0, m ≥ 0 }
    L2 is unambiguous.

A CF grammar that is not linear is nonlinear.
Lnl = {w: na(w) = nb(w)} is also a Non-Linear CFG.

-- 3. Non-Deterministic Context Free Language(N-CFG): For which only Non-Deterministic Push-Down-Automata(N-PDA) is possible e.g.
L3 = {wwR | w ∈ {a, b}* }
L3 is also Linear CFG.

--4. Ambiguous CFL: CFL for which only ambiguous CFG is possible
L4 = {anbncm | n ≥ 0, m ≥ 0 } U {anbmcm | n ≥ 0, m ≥ 0 }
L4 is both non-linear and Ambiguous CFG And Every Ambigous CFL subseteq N-CFL.

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?

Given Venn-diagram below:

enter image description here

Also asked here

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

"IN CONTEXT OF CHOMSHY CLASSIFICATION OF FORMAL LANGUAGE"

(1) L3 = {wwR | w ∈ {a, b}* }

  • Language L3 is a Non-Deterministic Context Free Language, its also Unambiguous and Liner language.

(2) Lp is language of parenthesis matching. There are two terminal symbols "(" and ")".
Grammar for Lp is:

S → SS
S → (S)
S → ()   
  • This language is nonlinear, deterministic and unambiguous too.

Language L that is union of Lp and L3 is unambiguous, nonlinear (due to Lp), and non-deterministic (due to L3) (Assuming language symbols for both languages are different).

This Language is an example of language in Venn-diagram for which I marked ??.

Also the correct diagram is below:

An ambiguous context free language also be a liner context free

dcf


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...