Recent questions tagged regular-languages

0 votes

1 answer

1

Practice Question
How to prove that $ (a+b)^*ab(a+b)^*+b^*a^* = (a+b)^*$

asked 5 days ago in Theory of Computation by Hardik Maheshwari (97 points) | 24 views

0 votes

0 answers

2

MadeEasy Test Series
$L^{*}-\{{\epsilon }\}=L^{+}$. True or False? (Given L is a language)

asked 5 days ago in Theory of Computation by CS.user (97 points) | 45 views

0 votes

0 answers

3

Made Easy Test
Which of the following RE are equivalent ? (a+b)*abb(a+b)* (a+b)*a(a+b)*bb(a+b)* (a+b)*ab(a+b)*b(a+b)*

asked 6 days ago in Theory of Computation by Shamim Ahmed Active (2.2k points) | 28 views

0 votes

0 answers

4

theory of autometa
let M be a finite autometa .let M' denote the machine obtained by interchanging the final and non final state L(M) U L(M') =sigma* L(M) $\cap$ L(M') =$\Phi$ i am sure that 1st is true but for 2nd take an example so 2nd become false but given that both are true for DFA where i am doing mistake ??

asked Jan 11 in Theory of Computation by Gurdeep Saini Loyal (7.7k points) | 30 views

0 votes

0 answers

5

Made Easy test series
L1 is regular, L2 and L3 are CFL L1 is regular, L2 is CFL and L3 is CSL L1 is CFL but not regular,L2 is CSL but not CFL,L3 is CFL L1, L2 and L3 are CFL

asked Jan 9 in Theory of Computation by Sambhrant Maurya Active (1.2k points) | 25 views

0 votes

0 answers

6

Made Easy test series

asked Jan 9 in Theory of Computation by Sambhrant Maurya Active (1.2k points) | 44 views

0 votes

0 answers

7

Regular Language
Which of the following option is correct regarding dependability? A. Given a regular language R and context-free C. Is every string in R also in C, i.e., Is L(R)⊆L(C) decidable? B. Given a regular language R and context-free C. Is every string in C also in R, i.e., Is L(C)⊆L(R) decidable? C. Both (A) and (B) D. None of these

asked Jan 7 in Theory of Computation by Shivangi Parashar 2 (329 points) | 21 views

0 votes

0 answers

8

Regular Language
If L ≠ ∅ and L is regular then L is the union of regular language A1, . . . , An where each Ai is accepted by a DFA with exactly one final state .Please elaborate how this statement is true.

asked Jan 7 in Theory of Computation by Shivangi Parashar 2 (329 points) | 30 views

0 votes

1 answer

9

Regular Expression Statements
Can anyone explain how S2 is false,I did not understand their logic.

asked Jan 1 in Theory of Computation by sripo Active (1.3k points) | 49 views

0 votes

1 answer

10

regular language
Stare true and false Is this regular ? now if it is not regular then i want to change in the question in place of (a+b)+ if it is (a+b)* then ??

asked Dec 31, 2018 in Theory of Computation by Gurdeep Saini Loyal (7.7k points) | 51 views

+1 vote

2 answers

11

NTA NET DEC 2018

asked Dec 30, 2018 in Theory of Computation by rakeshcoresoft (83 points) | 85 views

+1 vote

1 answer

12

Closure Properties
What is difference between Σ* and L* ? Which is true ? S1 : Σ* – {ϵ} = Σ+ S2 : L* – {ϵ} = L+ .

asked Dec 24, 2018 in Theory of Computation by anurag sharma (103 points) | 100 views

0 votes

0 answers

13

#TOC Regular Language Is this a regular set?
WXW^R where W,X belongs to (0,1)* W^R is reverse of a string!

asked Dec 22, 2018 in Theory of Computation by iarnav Loyal (9.4k points) | 47 views

0 votes

0 answers

14

UGC NET Doubt
https://gateoverflow.in/13365/ugcnet-dec2014-iii-24 i’ve a small doubt in the solution of this question how is (a+b)*ba(a+b)* complement of the given language?

asked Dec 14, 2018 in Theory of Computation by aditi19 Active (2.2k points) | 55 views

0 votes

1 answer

15

UGC NET 2016
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has _____ equivalence classes. pls give a detailed solution

asked Dec 14, 2018 in Theory of Computation by aditi19 Active (2.2k points) | 55 views

+1 vote

1 answer

16

TOC Which is(are) regular? Please explain 1 and 4.
Which of the following languages is regular? L = { bba (ba)* a^n-1 | n> 0 } L = {a^nb^n | n < 1000 } L = {a^nb^k | n is odd or k is even } L = {wxw^R | w,x ∈(0+1)* } 1, 3 and 4 2, 3, 4 2, 3 1, 2, 3, 4

asked Dec 13, 2018 in Theory of Computation by rahuljai (437 points) | 90 views

+2 votes

1 answer

17

Regular language
L={a^m b^n | m-n=even} Is this language a regular language?

asked Dec 12, 2018 in Theory of Computation by AIkiran01 (209 points) | 176 views

0 votes

0 answers

18

THEORY OF COMPUTATION
Let $L_1= (0+1)^* , L_2=(01^*0 +1^*) \text{ and } L3=(01^+0 +1^+ + \epsilon) $. If $L=L_1 \cap L_2 \cap L_3$ Then find the number of strings in $L$ which do not contain $11$.

asked Dec 10, 2018 in Theory of Computation by ROHIT SHARMA 5 (143 points) | 41 views

0 votes

0 answers

19

proving a language is regular based on two regular language over same $\Sigma$ (complicated)

asked Dec 9, 2018 in Theory of Computation by csenoob (21 points) | 28 views

0 votes

0 answers

20

going from equivalnce classes into a DFA
Hello all, I saw an interesting question and i was wondering how to solve it. basically the subject i am having trouble with is going from equivalence classes of $R_L$ to building a DFA. The question: L is a language over {0,1}, for which ... how do you go from equivalence classes to finding the DFA? don't understand it. thank you very much for your help

asked Dec 5, 2018 in Theory of Computation by csenoob (21 points) | 81 views

0 votes

0 answers

21

TOC: Regular v/s Not Regular
In the following question, Neither L1 is subset of L2, nor L2 is subset of L1, so i think their intersection should be disjoint and L1 INTERSECTION L2, should be phi which is a Regular language, hence, option (A) should be correct. The given solution:

asked Dec 1, 2018 in Theory of Computation by chauhansunil20th Active (4.1k points) | 36 views

+1 vote

0 answers

22

Can't understand the intution behind the shortcut
let the ∑ = {0,1} ===> strings possible are should be Binary strings. No.of States in Minimal DFA that accepts, Decimal( Binary String ) = 0 mod n in ACE coaching institute, i learned that For Decimal( Binary String ) = 0 mod n i) if n ... String ) = 0 mod x or 0 mod y neither x divides y nor y divides x either x is divides y or y divides x

asked Nov 30, 2018 in Theory of Computation by Shaik Masthan Veteran (50.4k points) | 92 views

0 votes

0 answers

23

Condition for regular language to be infinite
Given M = (Q,Σ,δ,q0,F) a DFA with n states. Prove: The language L(M) is infinite iff it contains a string with length t, where n ≤ t < 2n. Please provide a prove. I am not getting it from the resources available on the ... we can accept infinite no. of strings isn't it? Then why doesn't this condition suffice? Please point out where I am going wrong.

asked Nov 30, 2018 in Theory of Computation by MiNiPanda Boss (19.8k points) | 87 views

0 votes

0 answers

24

Theory of Computation
For a binary string x = a0a1 · · · an−1 define val(x) to be the value of x interpreted as a binary number, where a0 is the most significant bit. More formally, val(x) is given by How many minimum states will be in a finite automaton that accepts exactly the set of binary strings x such that val(x) is divisible by either 4 or 5. i m getting 5 states. ??

asked Nov 20, 2018 in Theory of Computation by Abhisek Tiwari 4 Active (3.6k points) | 51 views

+1 vote

1 answer

25

GATEBOOK-2019-TOC1-10
If $L$ is a regular language, which of the following is true? $L' = \{x_1x_3x_5 \ldots \mid x_0x_1x_2x_3x_4 \ldots \in L\}$ is non - regular $L'' = \{x_0x_2x_4 \ldots \mid x_0x_1x_2x_3x_4 \ldots \in L\}$ is non - regular Both $L'$ and $L''$ are non-regular Both $L'$ and $L''$ are regular

asked Nov 12, 2018 in Theory of Computation by GATEBOOK Boss (13.5k points) | 131 views

0 votes

1 answer

26

GATEBOOK-2019-TOC1-16
Consider the DFA with states $\{0,1,2,3,4\},$ input alphabet set $\{0.1\},$ start state $0,$ final state $0,$ and transition function $\delta \left ( q,i \right ) = (q^2-i) \mod 5 \mid i \in\{0,1\}. $The language accepted ... binary strings containing odd number of $0$'s Set of binary strings containing even number of $1$'s Set of binary strings containing odd number of $1$'s

asked Nov 12, 2018 in Theory of Computation by GATEBOOK Boss (13.5k points) | 80 views

+1 vote

1 answer

27

GATEBOOK-2019-TOC1-20
Let $L_1 = a^*b^*$ and $L_2 = \{ab\}.$ $L_3 = \text{Prefix}(L_1^* \cap L_2),$ where $\text{Prefix}(L) = \{u \mid uv \in L$ for some $v\}.$ Number of strings in $L_3$ is _______

asked Nov 12, 2018 in Theory of Computation by GATEBOOK Boss (13.5k points) | 126 views

0 votes

0 answers

28

RE for given FA
The correct regular expression for the below mentioned Finite Automata Do we have to have ca* as C is dead state,does dead state be a part of regular expression? The expression I am gettting is c*a(d*+ba*) as C state is dead state hence no need to consider it.Please Correct me.

asked Nov 6, 2018 in Theory of Computation by sripo Active (1.3k points) | 55 views

0 votes

1 answer

29

Are these two languages equal?
L1=ab* L2=a(aa)*b(bb)* Are the languages equal if not what relation do they satisfy?

asked Nov 6, 2018 in Theory of Computation by sripo Active (1.3k points) | 31 views

0 votes

0 answers

30

This question is taken from a sample paper
Consider the following grammar G. Is this regular? S →EF E → a|∈ F → abF|ac

asked Nov 3, 2018 in Theory of Computation by Piyush Agarwal 1 (15 points) | 14 views

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

Recent questions tagged regular-languages

Recent Posts

Recent Blog Comments