date: 2024-11-07
title: 06-TOC-CFL
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- CFL
publish: True
TOC-Context Free Language
A context-free grammar (CFG) is a 4-tuple
A language is context-free if exactly all strings in the language can be produced by a context-free grammar.
A language is context-free if and only if it is recognized by a PDA.
A parse tree shows the structure of a string (sentence). However, CFG is strongly enough to create ambiguous.
A grammar is ambiguous if a string in the language defined by the grammar can be presented by multiple parse trees with different structures.
Also, checking whether a CFG is ambiguous is undecidable.
Meaning that there is NO algorithm / machine which can tell an arbitrary CFG is ambiguous or not.
A language is context-free if and only if it is recognized by a PDA.
Let
By the definition of CFL,
Then, we prove the theorem by introducing a conversion algorithm from
To construct the PDA
In detail, P does the following things.
Formally, let
The PDA is called parser, which is used in compilers.
Now let's convert an arbitrary PDA
First, we modify
Formally, Let