The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

Please ANSWER these?

asked in Theory of Computation by Veteran (20.3k points) | 182 views
1: Regular

2: Regular


@ Ankit Srivastava 7   How 3rd one is DCFL and not CFL?

If it is DCFL then obviously it is CFL

I am not saying it is not CFL

DCFL is subset of CFL

if you want most accurate answer then it will be DCFL

see L1={a^n b^m | n=m} is complement of given language

and this language is DCFL and DCFL's are closed under this language is also DCFL

Ankit Srivastava 7  Thanks bro!

1 Answer

+2 votes
Best answer

A)$L_{1}=\left \{ a^{n}\,|\, n> 0 \right \} L_{2}=\left \{ b^{n}\,|\, n> 0 \right \}$

Regular language are closed under Concatenation.Hence regular 

$L_{1}.L_{2}=\left \{ a^{x}b^{y}\,\,|\,\,x,y > 0 \right \}$

Regular expression-:$a^{+}b^{+}$

B)$L_{2}=\left \{ a^{n}b^{m}\,\,|\,\,n,m \geq 0 \right \}$

Regular Expression-:$a^{*}b^{*}$

Hence regular

C) Not regular need a stack to remember $n$,Thus can't be solved by FSM

Hence not regular 

answered by Veteran (17.9k points)
selected by

@sourav Whoa! Thanks, that was quick! Keep up, mate. Thanks again.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,241 questions
40,932 answers
39,846 users