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

by

“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

More Related Contents:

  1. Left-Linear and Right-Linear Grammars
  2. Need Regular Expression for Finite Automata: Even number of 1s and Even number of 0s
  3. Regular expression [ 1 ( 0 1* 0)* 1 ]* DFA
  4. Can regular expressions be used to match nested patterns? [duplicate]
  5. Why can’t C++ be parsed with a LR(1) parser?
  6. Is there a typical state machine implementation pattern?
  7. Is it possible for a computer to “learn” a regular expression by user-provided examples?
  8. Finding the complement of a DFA?
  9. Tips for creating “Context Free Grammar”
  10. Regular vs Context Free Grammars
  11. Grammatical inference of regular expressions for given finite list of representative strings?
  12. What is the language of this deterministic finite automata?
  13. How does “δ:Q×Σ→Q” read in the definition of a DFA (deterministic finite automaton)?
  14. Is a*b* regular?
  15. What kind of formal languages can modern regex engines parse?
  16. Design DFA accepting binary strings divisible by a number ‘n’

Leave a Comment