need answers with explanation. need it in 1 hr......................................................................................................................

CSCE 4115 ASSIGNMENT #4Due Wednesday, October 26, 20161. Design a context-free grammar and a pushdown automaton for each of the following languages.The PDA’s should be deterministic if possible. If it is not possible to write a DPDA, give aninformal justification for your claim (i.e., L is a NCFL). For each CFG and PDA you write,give an informal explanation of how and why the CFG/PDA works. Also, for each CFG,give two sample derivations to further demonstrate the correctness of your grammar, and foreach PDA, run the PDA in Prolog with two correct and two incorrect strings. For the samplestrings, use the strings included in the problem statement.(a) L ={w|w∈ {a,b,c,d}+, w contains an equal number of a’s and b’s or an equal numberof c’s and d’s}. Example strings include aabbccdd, dabcbcd, and dabcab.(b) L ={w|w∈ {0,1}*, w is a list of unary integers separated by 1’s that arenotinascending order}. For example, 00010010000 is in L but 01001000 is not.(c) L ={aibjxck|(i=k∧x= 0)∨(j=k∧x= 1),i,j,k≥0}. Example strings in thislanguage includeaab0cc,aaab1c,aa0cc,bbb1ccc, and∅.2. Consider the pushdown automaton below:M = ({q0,q1},{0, 1},{X, Z},δ,q0, Z,∅)δ(q0, 1, Z) ={(q0, XZ)}δ(q0, 1, X) ={(q0, XX)}δ(q0, 0, X) ={(q1, X)}δ(q0,ε, Z) ={(q0,ε)}δ(q1, 1, X) ={(q1,ε)}δ(q1, 0, Z) ={(q0, Z)}Give a context-free grammar which generates L(M). Describe the language L in English and/orset notation.3. Prove that the following are not context-free languages.(a) L ={w|w is a string of the form (0*1)*, with all sets of 0’s the same length}. Thestrings of this language areε, 0101, 001001, 00010001, ....(b) L ={0n!|n≥0}. The strings of this language are 0, 00, 000, 000000, 024, etc.(c) L ={w|w∈ {0,1}*, w contains no string of the form xxR}.4. Consider the grammar G with productions as follows:S→AD|BCA→aB→bC→a|AS|BED→b|BS|AFE→CCF→DDUse the CYK algorithm to test membership ofabbaba.

• 1495077281-aa.pdf

SuperTutor

(15)

Status NEW Posted 18 May 2017 03:05 AM My Price 9.00

-----------

Attachments

file 1495077287-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer