Skip to main content

Automata and Formal Language Question Answer

1. Construct CFG for the following Languages:
a) Set of all binary strings where number of 0’s are greater than number of 1’s.
2. Prove that the following CFGs are ambiguous:
a) 𝑆 β†’ π‘Žπ‘†π‘ | 𝑆𝑆| πœ–
b) 𝑆 β†’ π‘†π‘Žπ‘† |𝑆𝑏𝑆 |𝑐
c) 𝑆 β†’ π‘Žπ΅ | π‘Žπ‘, 𝐴 β†’ π‘Žπ΄π΅|π‘Ž, 𝐡 β†’ 𝐴𝐡𝑏 |𝑏
3. Convert the following CFGs into their equivalent Chomsky Normal Form:
a) 𝑆 β†’ 𝐡𝑆𝐡 | 𝐡 πœ–, 𝐡 β†’ 00 πœ–
b) 𝑆 β†’ 𝑏𝐴 |π‘Žπ΅ , 𝐴 β†’ 𝑏𝐴𝐴|π‘Žπ‘† π‘Ž , 𝐡 β†’ π‘Žπ΅π΅ | 𝑏𝑆 | b


For Solutions Click in the Download Button:

Download Solutions
Labels:

Comments

Post a Comment

Popular posts from this blog

Postfix Evaluation(Single or Multi Digit) using STACK in C

POSTFIX EVALUATION WITH SINGLE OR MULTI DIGIT: Students find difficulties in finding the correct code for Postfix evaluation using Stack which works for Single as well for multidigit also; So here is the Question Format Given::- Question_2; Data_Structure:  Write a C program to evaluate the following POSTFIX expression. Use STACK to solve this problem.  INPUT: 5 6 2 + * 12 4 / -  OUTPUT: 37 Basic Understanding: Here is the Correct code:
1 comment
Read more

STACK in C

IMPLEMENTATION OF STACK USING ARRAY Here is Example of Source Code of Data Structure-1, Question 1: Data_structure :  Write a C program to implement STACK using an array. This program must include the following functions in it. Write a function for β€œPush” operation.   Write a function for β€œPop” operation.  Write a function for β€œDisplay” operation which prints the content of the STACK.    Basic Understanding : Push and Pop Operation: Here is How to Implement:                                                   
4 comments
Read more

Combinatorics For Programmers and Coders

Hey! Computer Geeks! Here we will discuss two or more special numbers that made the way of coding easy, Introduction to Catalan Numbers: The Catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics. They count certain types of lattice paths, permutations, binary trees, and many other combinatorial objects. They satisfy a fundamental recurrence relation and have a closed-form formula in terms of binomial coefficients. The Catalan number Cn describes, among other things: The number of binary trees with n nodes, The number of ways in which parentheses can be placed in a sequence of n+ 1 numbers to be multiplied two at a time, The number of well-formed reverse Polish expressions with n operands and n + 1 operators, The number of paths in a grid from (0, 0) to (n, n), increasing just one coordinate by one at each step, without crossing the main diagonal,  The number of n-bit sequences that the number of 1s never exceeds the n...
1 comment
Read more