search
Log In
0 votes
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$
in Theory of Computation 40 views

Please log in or register to answer this question.

Related questions

0 votes
0 answers
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\}.$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 59 views
0 votes
0 answers
2
25 views
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.$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 25 views
0 votes
0 answers
3
51 views
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.
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 51 views
0 votes
0 answers
4
17 views
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.$
asked Apr 6, 2019 in Theory of Computation Lakshman Patel RJIT 17 views
...