# Recent questions tagged expression

1
Can anyone explain how S2 is false,I did not understand their logic.
2
Can you please draw the DFA for given regex (ab*)*
3
Ans. C
4
Can someone please explain me how could we derive the RE from FA's ... Here-- https://gateoverflow.in/464/gate2008-52 PS- Obviously the answer can be easily obtained using parsing, but how can we derive the regular expression?? Ardent is too lengthy for exam point of view, so explanation with some other technique like state elimination will be appreciated...
5
6
7
Find the time complexity of the following snippets 1. for$\left ( i=1;i\leqslant n;i++ \right )$ for$\left ( j=n/3;j\leqslant 2n;j=j+n/3 \right )$ $x=x+1;$ 2. for$\left ( i=1;i\leqslant n;i++ \right )$ for$\left ( j=1;j\leqslant n;j=j+i \right )$ $x=x+1;$
8
The equality of two regular expression is computed in? Give reasons also.. Constant Time polynomial time logarithmic Polynomial time Exponential time
9
The infix expression $A+(B-C)^*D$ is correctly represented in prefix notation as $A+B-C^*D$ $+A^*-BCD$ $ABC-D^*+$ $A+BC-D^*$
1 vote
10
If r1 and r2 are 2 Regular Expression Such that r1 = (a+b)* r2 = (a*+b*+a*b*+b*a*) What are the different case's in which r1 = r2 ? Please Explain with an example
11
Problem 1 : what is the Language associated with this regular expression ? a*b* write it down. Problem 2: Does either a subset or Super-set of a regular language is always a regular ? Problem 3 : What is the difference between a^n b^n and a*b* Explain with a example .
The context free grammar given by $S \rightarrow XYX$ $X \rightarrow aX \mid bX \mid \lambda$ $Y \rightarrow bbb$ generates the language which is defined by regular expression: $(a+b)^*bbb$ $abbb(a+b)^*$ $(a+b)^*(bbb)(a+b)^*$ $(a+b)(bbb)(a+b)^*$