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

Comments

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:

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:                                                   

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 numbe