Understanding Deterministic Context-Free Languages
Discover the concept of Deterministic Context-Free Languages (DCFL) - a subset of context-free languages accepted by Deterministic Push-Down Automata. Learn about their properties, importance, and examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
DETERMINISTIC CONTEXT FREE LANGUAGES Ethakota Krishnamurthi Surendranath Manoj Gujjari
What is a CFL(Context Free Language)? Deterministic Context Free Language Description Properties Importance
CONTEXT FREE LANGUAGES A context-free language (CFL) is a language generated by some context-free grammar (CFG). Different CF grammars can generate the same CF language, or conversely, a given CF language can be generated by different CF grammars. The class of context-free languages generalizes the class of regular languages, i.e., every regular language is a context- free language. The reverse of this is not true, i.e., every context-free language is not necessarily regular.
DCFL Deterministic context-free languages are a proper subset of context-free languages. Context free languages that can be accepted by Deterministic Push-Down Automata. DCFLs are always unambiguous. Many programming languages can be described by means of DCFLs.
DCFL Description Consider $: end of string marker Consider an example: Let L = a* {anbn: n > 0}. When it begins reading a s, M must push them onto the stack. In case there are going to be b s it runs out of input without seeing b s, it needs a way to pop the a s from the stack before it can accept. The end-of-string marker allows the popping to happen, when all the input has been read. Add $ to make it easier to build DPDAs, it does not add power (to allow building a PDA for L that was not context-free) There exist CLFs that are not deterministic, e.g., L = {aibjck, i j or j k}.
A DETERMINISTIC PDA FOR L L = a* {anbn : n > 0}.
A NDPDA FOR L( No end-marker) L = a* {anbn : n > 0}.
Properties of DCFL DCFLS are not closed under union. DCFLS are not closed under intersection. DCFLS are closed under complement.
DCFLS are not closed under UNION L1 = {aibjck, i, j, k 0 and i j}. L2 = {aibjck, i, j, k 0 and j k}. (a DCFL) (a DCFL) L = L1 L2. = {aibjck, i, j, k 0 and (i j) or (j k)}. L = L . = {aibjck, i, j, k 0 and i = j = k} {w {a, b, c}* : the letters are out of order}. L = L a*b*c*. = {anbncn, n 0}. L is not even CF, much less DCF.
DCFLS are not closed under Intersection L1 = {aibjck, i, j, k 0 and i = j}. L2 = {aibjck, i, j, k 0 and j = k}. L = L1 L2 = L1 and L2 are deterministic context-free:
References Automata, Computability and Complexity, Elaine Rich. http://en.wikipedia.org/wiki/Deterministic_context- free_language http://en.wikipedia.org/wiki/Context-free_language http://en.wikipedia.org/wiki/Unambiguous_grammar
