University:
California State University, Northridge
Course:
COMP 310 | Automata, Languages and Computation
Academic year:

2024
Views:

394

Pages:

2
Author:

Samuel K.

Problem 1. (10 points) Give a short simple description of the language generated by the CFG below. S -> Sa | aSb | bSa | SS | λ {w∈{a,b} ∗ :# a ≥# b } Problem 2. (10 points) Remove useless variables (equivalently productions) from the CFG below. S -> DEAD | Fa | FS A -> aDE + SSb + ba B -> aEAb + GbG + Bb C -> -Aa | -bA D -> ABC | FAFb | Ca | Cbaba E -> -ESa + BaG | BE F -> AB | FF | aS | abba | G -> BEG | aGE | Bab Generating SA, D, F, C Reachable S, A, D, F, C Not Reachable BEG Not Generating ACD Problem 3. (10 points) Construct an NPDA that accepts (a^i b^j c^k: i+2j-3k<0). ..... The main part of the image is a graphical representation of the NPDA. It consists of states (represented by circles), transitions labeled with input symbols and stack operations, and a start state indicated by an incoming arrow. The specific transitions and stack operations are not fully legible in the provided image.