Understanding Grammar #2: Ambiguity, Elimination, and Boolean Expressions

Click For Summary
SUMMARY

The discussion focuses on the analysis of two grammars: Grammar #1, which generates strings like (a,a) and (a,(a,a)), and Grammar #2, which defines boolean expressions using constructs like 'or', 'and', 'not', 'true', and 'false'. Participants question the ambiguity of Grammar #2 and seek methods for eliminating this ambiguity, as well as proving that it generates all possible boolean expressions. Key points include the distinction between terminals and non-terminals, and the correct interpretation of symbols used in boolean logic.

PREREQUISITES
  • Understanding of context-free grammars and their components
  • Familiarity with boolean algebra and logical operators
  • Knowledge of programming language syntax and semantics
  • Basic concepts of ambiguity in formal languages
NEXT STEPS
  • Study formal language theory, focusing on context-free grammars
  • Learn about techniques for eliminating ambiguity in grammars
  • Explore boolean algebra and its representation in programming languages
  • Research methods to prove the completeness of grammars in generating expressions
USEFUL FOR

Computer science students, programming language designers, and anyone interested in formal language theory and boolean logic.

magneeto
Messages
6
Reaction score
0
what langugage??

grammar #1:

S->(L)|a
L->L,S|S

what language does this grammar generate? some strings generated by this grammar r (a,a), (a,(a,a))...

grammmar #2:

bexpr->bexpr or bterm| bterm
bterm-> bterm and bfactor| bfactor
bfactor-> not bfactor| (bexpr) | true | false

is this grammar ambiguous? if so then why?
is there any way to eliminate ambiguity?
how do i show that this grammmar generates all boolean expressions? i can see it but how do i proceed to prove it?
 
Computer science news on Phys.org
when you type L,S do you mean LS
and when you type or and and are you using the booleans | and &
(|| and &&,the hat and the v whichever notation you like )
what do the brackets () normally represent in programming
ask your self what is an ambiguity and what are "terminals"
what do the rules bexpr and bterm attempt represent
how does one normally write boolean logic?? or concatenate sets of booleans
 
",","()","a" are all terminals and "|" is not the logical or . it is the or for regular expressions(either expr1 or expr2)
 

Similar threads

MHB Construct grammar and find its type
  • · Replies 26 ·
Replies
26
Views
2K
Comp Sci Complexity for generating strings of length k from CNF grammar
  • · Replies 3 ·
Replies
3
Views
2K
Understanding Ambiguity in If-Else Grammars: An Explanation and Analysis
  • · Replies 12 ·
Replies
12
Views
3K
A Chat with ChatGPT: Peerless Intelligence
  • · Replies 3 ·
Replies
3
Views
3K
MHB Is the Complexity of Satisfiable Boolean Expressions in NP?
  • · Replies 1 ·
Replies
1
Views
2K
How Do You Construct a Parse Tree for the Expression (a, (a, a))?
  • · Replies 3 ·
Replies
3
Views
2K
Comp Sci Validating Braces Placement for Expression Evaluation
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Tong Dynamics: cannot cancel angle from orbit energy expression calculation
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Addition of angular momenta
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Orthonormal basis expression for ordinary contraction of a tensor
  • · Replies 2 ·
Replies
2
Views
2K