I recently wrote a rather long article on this topic: The true power of regular expressions. To summarize: Regular expressions with support for recursive subpattern references can match all context-free languages (e.g a^n b^n). Regular expressions with lookaround assertions and subpattern references can match at least some context-sensitive languages (e.g. ww and a^n b^n c^n). … Read more
“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 … Read more
How to write CFG with example ambn L = {am bn | m >= n}. Language description: am bn consist of a followed by b where number of a are equal or more then number of b. some example strings: {^, a, aa, aab, aabb, aaaab, ab……} So there is always one a for one … Read more
Constructing an equivalent Regular Grammar from a Regular Expression First, I start with some simple rules to construct Regular Grammar(RG) from Regular Expression(RE). I am writing rules for Right Linear Grammar (leaving as an exercise to write similar rules for Left Linear Grammar) NOTE: Capital letters are used for variables, and small for terminals in … Read more
LR parsers can’t handle ambiguous grammar rules, by design. (Made the theory easier back in the 1970s when the ideas were being worked out). C and C++ both allow the following statement: x * y ; It has two different parses: It can be the declaration of y, as pointer to type x It can … Read more