# Ullman (TOC) Edition 3 Exercise 5.1 Question 2 (Page No. 182)

40 views

The following grammar generates the language of regular expression $0^{*}1(0+1)^{*}:$

$S\rightarrow A1B$
$A\rightarrow 0A|\in$
$B\rightarrow B|1B|\in$

Give leftmost and rightmost derivations of the following strings$:$

1. $00101$
2. $1001$
3. $00011$

## Related questions

1
59 views
Let $T=\{0,1(,),+,*,\phi,e\}.$ We may think of $T$ as the set of symbols used by regular expressions over alphabet $\{0,1\};$ the only difference is that we use $e$ for symbol $\in,$ to avoid potential confusion in what follows. Your task is to design a CFG with set of terminals $T$ that generates exactly the regular expressions with alphabet $\{0,1\}.$
We defined the relation $\overset{*}\Rightarrow$ with a basis $"\alpha\Rightarrow \alpha$ and an induction that says $\alpha\overset{*}\Rightarrow\beta$ and $\beta\Rightarrow\gamma$ imply $\alpha\overset{*}\Rightarrow\gamma.$ There are several other ways to define ... $:$ Use induction on the number of steps in the derivation $\beta\overset{*}\Rightarrow\gamma.$
A CFG is said to be right-linear if each production body has at most one variable and that variable is at the right end. That is all productions of a right-linear grammar are of the form $A\rightarrow wB$ or $A\rightarrow w$ where $A$ and $B$ are ... form. Show that every regular language has a right-linear grammar. Hint$:$Start with a DFA and let the variables of the grammar represent states.
Design context-free grammars for the following languages$:$ The set $\{0^{n}1^{n}|n\geq 1,\}$that is the set of all strings of one or more $0's$ followed by an equal number of $1's.$ The set $\{a^{i}b^{j}c^{k}|i\neq j or j\neq k\},$that is ,the set of strings ... $ww,$ that is, not equal to any string repeated. The set of all strings with twice as many $0's$ as $1's.$