Log In
0 votes

Though n is finite, how we will compare a and c. My answer is D, but C is provided as the answer.

in Theory of Computation 94 views

we can write this in terms of regular expressions

like a1b+c1 + a2b+c2 +.............+ a99b+c99  , this is finite, So it should be regular

Hmm, nice approach.

1 Answer

0 votes
If there would have been no upper bound on $n$, then $L$ would be context free. Here there is an upper bound to $n$ and therefore our language here is finite. All finite languages are regular. Also, all regular languages are context free.

Therefore given language is regular and context free. Ans is (C)

Related questions

2 votes
1 answer
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked Apr 30, 2019 in Theory of Computation srestha 390 views
0 votes
1 answer
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________ Answer will be $3$ or $6?$
asked Apr 23, 2019 in Theory of Computation srestha 307 views
0 votes
3 answers
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ ... Recursive $(B)$ Non-Recursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked Apr 13, 2019 in Theory of Computation srestha 2k views
–1 vote
1 answer
Consider the given below languages L1 and L2. L1= {pnqmrmsn | m,n ≥ 0} L2= {pnqnrmsm | m,n ≥ 0} Select the correct statement about, L such that L= (L1 U L2 ) – (L1 ꓵ L2 ) 1. L is CFL but not DCFL 2. L is regular 3. L is CSL but not CFL 4. L is DCFL but not regular i know that L is representing the EX-OR of L1 and L2, couldn't visualize as how it will be cfl. please help.
asked Nov 9, 2018 in Theory of Computation aambazinga 200 views