Hello guys. Please help me with a problem # 2! Thanks very much! Section 13.1 Co

Question

Hello guys. Please help me with a problem # 2! Thanks very much! Section 13.1 Construct a type-2 phase-structure grammar defining the set of all bit strings of the form 1*0^a1^b s.t. a > b. This could be described as the set of all words that start with 0 or more 1's, then has a bunch of 0's followed by a bunch of 1's such that there are more 0's than the following 1's. Section 13.2: Construct a finite-state machine that reads bit strings and outputs a word that is the same as the input word in every other bit (starting with the first), but that changes every other bit (starting with the second bit). For example, if the input was 10011010010, the output would be 11001111000.

Explanation / Answer

Type -2 grammar or context free grammar (cfg): It can be in the form of production rules

A -> YaZ

B-> YZ

Y -> a

Z-> b

where A,B,Y,Z are Non terminals and a,b are terminals.

-> given language is L(G) ={ 1*0a1b such that a>b .}

1,0 are terminals.

L(G) should accept strings only like 001,1001,0001,10001,00011,100011,...etc.

-> it starts with 0 or 1 ,later number 0's is more than followed by number of 1's .

-> Required CFG is

Let start symbol is S

S -> 0MR | 1L

L -> 0MR | 1L

M -> AM | A

R -> AR | B

A -> 0

B -> 1

where S,A,B,L,M,R are Nonterminals.and 0,1 are terminals.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.