Give a CFG for L = { x#y : x,y in {0,1}* |x| ≠ |y| }

  • Comp Sci
  • Thread starter shivajikobardan
  • Start date
In summary, the conversation discusses a solution approach for creating a cfg for the languages L1, L2, L3, and L4. The approach involves breaking down the language specifications into simpler ones and then unionizing them. It is mentioned that the breakdown should include the '#' terminal and that the constructs 0m1n and 1m0n are not present in the original specifications. The speaker also asks for confirmation on the correctness of the approach.
  • #1
shivajikobardan
674
54
Homework Statement
Give a CFG for L = { x#y : x,y in {0,1}* |x| ≠ |y| }
Relevant Equations
None
1636786865541.png


Is my this solution approach correct? I am thinking of making cfg for L1 U L2 U L3 U L4

Where L1=0^m 1^n ----------->m>n

L2=L1 for m<n

L3=1^m 0^n ---->m>n
L4=L3 for m<n

Is my approach correct? If I can do it like that then this will be easy problem for me as well.
 
Physics news on Phys.org
  • #2
You are free to decompose a language specification into simpler specifications that can be unionized provided that you get the same specification. Your breakdown does not address the '#' terminal. I also don't see where you are getting 0m1n or 1m0n constructs from the original specification.
 
Last edited:

FAQ: Give a CFG for L = { x#y : x,y in {0,1}* |x| ≠ |y| }

What is a CFG?

A CFG stands for Context-Free Grammar, which is a formal grammar used to generate strings in a language. It consists of a set of production rules that specify how symbols can be combined to form strings.

What does L = { x#y : x,y in {0,1}* |x| ≠ |y| } represent?

This notation represents a language, L, that consists of all strings of the form x#y, where x and y are strings of 0s and 1s, and the length of x is not equal to the length of y.

How do you give a CFG for L = { x#y : x,y in {0,1}* |x| ≠ |y| }?

A CFG for this language can be given by the following production rules:

S → 0S1 | 1S0 | #

#S → ε

S → 0 | 1

Can you give an example of a string that belongs to L = { x#y : x,y in {0,1}* |x| ≠ |y| }?

One example of a string that belongs to this language is "001#11". This string consists of x = "001" and y = "11", where the length of x is not equal to the length of y.

Is there a way to prove that a string belongs to L = { x#y : x,y in {0,1}* |x| ≠ |y| }?

Yes, there are a few ways to prove that a string belongs to this language. One way is to use the given CFG and show that the string can be generated by the production rules. Another way is to use mathematical induction to show that the string follows the given pattern of x#y, where the length of x is not equal to the length of y.

Similar threads

Capacitance and Inductance questions
Replies
29
Views
4K
Infinite loop iterating over a linked list
Replies
17
Views
1K
Analytical kinematics of a 6-bar mechanism
Replies
2
Views
2K
Can Anyone Help with Simple C Programming in Ax=B Homework?
Replies
4
Views
1K
Comp Sci Expected number of collisions for hashing with chaining
Replies
1
Views
2K
How Do You Compute p(Z > l2) in Exponential Distributions?
Replies
2
Views
2K
Engineering Mutual Inductance between two conductors
Replies
2
Views
1K
MHB Express X in terms of L1, L2 and L3. Circle within Circle.
Replies
1
Views
907
O(log k) GCD Algorithm which yields x and y |GCD(a,b)=ax+by
Replies
1
Views
1K
Decide the resulting force (F) per meter on L2
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top