Recent questions tagged toc-languages

Recent questions tagged toc-languages

0 votes

1 answer 45 views

TOC - Regular Expressions
As for a Finite Automata, we say a finite automata accepts a language if it accepts all strings present in the language as well as REJECTS all strings which are not present in the language. Is the definition for a regular language the same as that ... all strings of the regular language as well as NOT represent any strings not part of the language ?? Pls clear this.

Rutuja Desai asked in Theory of Computation Oct 27

by Rutuja Desai

5 points

45 views

0 votes

1 answer 57 views

Gate Academy toc self douht
Caption I draw a DFA of given language.is it true or false? If i false then send me right one.

Enolx.21 asked in Theory of Computation Sep 8

53 points

57 views

0 votes

1 answer 40 views

applied gate test
how many states are in smallest possible DFA {0,1} * {$1^{10}$}

Nilabja Sarkar asked in Theory of Computation Aug 30

by Nilabja Sarkar

5 points

40 views

0 votes

0 answers 173 views

Countability in toc
Hi What is best resource and Where to study countability topic in toc?

ykrishnay asked in Theory of Computation Aug 21

103 points

173 views

0 votes

0 answers 31 views

How to design Turing machine for addition of 2 binary numbers

ykrishnay asked in Theory of Computation Aug 18

103 points

31 views

1 vote

0 answers 37 views

complement of language
How to find complement of language.? complement of recursive language is recursive. while complement of context free language is context sensitive language.

TheShivam asked in Theory of Computation Aug 16

9 points

37 views

0 votes

0 answers 33 views

Regular Grammar
Is S--> AccB A-->aA/a B-->bB/a a regular grammar according to the type 3 grammar rule i.e, production must be in the form S-->Ax or S-->xA where A is non terminal and x is terminal?

Shubhranshu asked in Theory of Computation Aug 1

5 points

33 views

0 votes

0 answers 31 views

Clear distinction between Finite automata, Regular expressions

akshansh asked in Theory of Computation Jun 12

15 points

31 views

0 votes

0 answers 43 views

NPTEL(Theory of Computation )
How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?

hrtoimukra asked in Theory of Computation Jun 9

5 points

43 views

0 votes

1 answer 16 views

#Self_Doubt #NFA
For any given NFA with ip_set = {a,b} if any transaction is Missing then can we assume a Self Loop ? For example, [T1] a b [T2] a b S S,P Q S S,P Q is P _ Q same as P P Q Q* _ _ Q* Q Q Notice in T1 for transaction(P,a) = undefined. So can we assume transaction(P,a) = P ?

Palash_292 asked in Theory of Computation May 18

5 points

16 views

0 votes

0 answers 25 views

$r^+$ and $r^*$doubt from TOC[self doubt]
if $r= a+epsilon$, then the $r^+$ and $r^*$ will be same right? in a question i was solving it is asked, $r^*=r^+$ if and only if $r=epsilon$. Is this true or false as i have written an example above where $r^*$ and $r^+$ will be same.

rythmrana asked in Theory of Computation May 16

5 points

25 views

1 vote

0 answers 21 views

Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.

Setsu asked in Theory of Computation May 3

by Setsu

13 points

21 views

1 vote

0 answers 15 views

Peter Linz 6th Edition Chapter 3 Exercise 3.3 Q 4
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.

Setsu asked in Theory of Computation May 3

by Setsu

13 points

15 views

0 votes

0 answers 27 views

Ullman,rozen
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w

Gogo6996 asked in Theory of Computation May 2

5 points

27 views

0 votes

0 answers 21 views

DFA construction
For E={a,b} construct a dfa for language L where L={w | w has a b in its 2nd last position if such a position exists}????

harshit_1010 asked in Theory of Computation May 2

by harshit_1010

5 points

21 views

0 votes

0 answers 20 views

#DFA Introduction, Formal Languages, DFA Construction examples

DarkShadow18 asked in Theory of Computation Apr 10

by DarkShadow18

5 points

20 views

0 votes

0 answers 36 views

AppliedGate lecture example
What is the NFA that does not accept strings ending “101” ?

shri385 asked in Theory of Computation Apr 7

5 points

36 views

0 votes

0 answers 35 views

PDA for a^nb^n/n>=1
Is this PDA correct for a^n. B^n/n>=1?

jaswanth431 asked in Theory of Computation Mar 4

5 points

35 views

2 votes

1 answer 48 views

Self Doubt on Theory of Computation
What is the intersection of recursive and recursively enumerable language?

samir757 asked in Theory of Computation Mar 4

29 points

48 views

0 votes

1 answer 57 views

Context Free Languages (Self Doubt)
I understand that the language L = {a^m b^n c^k|(m=n)or(n=k)} is CFL because it can be represented as the union of L1 = {a^m b^m c^k} and L2 = {a^m b^k c^k} which are both CFL's. But I can't figure out the working of the PDA accepting L. To check ... meaning (m=n) or (m-n) a's or (n-m) b's will remain in the stack meaning (m!=n). How can we check for (n=k) now?

shantanu4raje asked in Theory of Computation Feb 6

by shantanu4raje

25 points

57 views

0 votes

0 answers 41 views

made easy test series
Answer given is “All of these” My answer is none of these are regular.

rahul65 asked in Theory of Computation Feb 3

5 points

41 views

0 votes

0 answers 69 views

TOC Made easy
Consider the grammar consisting of seven productions. S → aA | aBB A → aaA | λ B → bB | bbC C → B After elimination of unit, useless, and λ -productions how many productions remain in the resulting grammar ? 2 3 4 5

kirtipurohit asked in Theory of Computation Feb 2

by kirtipurohit

15 points

69 views

0 votes

0 answers 62 views

Gate Overflow itself
Is the explanation is correct? Link-https://gateoverflow.in/33183/complement-of-csl If I say complement of $a^{n}b^{n}c^{n} \, \, \, \, \, \, is\, \, \, \, \, a^{n}b^{n}c^{m} \: \: and\: \: \: m\neq n$ Then How Can it be regular?

RavGopal asked in Theory of Computation Feb 1

145 points

62 views

0 votes

0 answers 49 views

self doubt - decidability
L={<M>| M is a TM that accepts all even numbers}. How to check whether it is RE, REC or not RE… I think Rice’s theorem 2nd part is not applicable here

Abhineet Singh asked in Theory of Computation Feb 1

by Abhineet Singh

23 points

49 views

1 vote

0 answers 55 views

Recursive Languages Self Doubt
Is recursive language closed under positive closure?

aditi19 asked in Theory of Computation Jan 29

59 points

55 views

0 votes

0 answers 40 views

Madeeasy Test series TOC Q1

Shivateja MST asked in Theory of Computation Jan 23

by Shivateja MST

45 points

40 views

0 votes

0 answers 18 views

An introduction to formal languages and automata
How can I explain that this language- L= { a<sup>n</sup> b<sup>l</sup> : n ≠ l } is not regular. [USE PUMPING LEMMA OR CLOSURE PROPERTIES] This question is under a book named An introduction to ... understandable manner and show how you exactly arrived at the solution? That would be a great help to me. Thanks in advance

kirtipurohit asked in Theory of Computation Jan 18

by kirtipurohit

15 points

18 views

0 votes

1 answer 36 views

Show that the language S-> aSS| b is not regular ?

kirtipurohit asked in Theory of Computation Jan 18

by kirtipurohit

15 points

36 views

0 votes

0 answers 80 views

An introduction to formal languages and automata peter linz

kirtipurohit asked in Theory of Computation Jan 16

by kirtipurohit

15 points

80 views

0 votes

0 answers 17 views

Peter Linz 5e Ex-2.1 Q-7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }

aditi19 asked in Theory of Computation Jan 14

59 points

17 views

1 vote

0 answers 39 views

Peter Linz 5e Ex-2.1 Q7e DFA
Find DFA on $\Sigma =(a,b)$ for L={ w : $(n_{a}(w)-n_{b}(w))mod3>0$ }

aditi19 asked in Theory of Computation Jan 14

59 points

39 views

0 votes

1 answer 33 views

Applied Test Series TOC
Options: My answer was: D answer according to them was B and D and their explaination was

Nitinkumar.097 asked in Theory of Computation Jan 4

by Nitinkumar.097

13 points

33 views

0 votes

0 answers 37 views

GATE 2003 , Theory Of Computation , Turing Machine

Pushkar Khadase asked in Theory of Computation Jan 4

by Pushkar Khadase

5 points

37 views

0 votes

3 answers 61 views

youtube exercise unacademy
L1=a^n,,n>0 L2=a^n b^n c^n , n>0 L1.L2 is a)regular b)cfl c)csl d)none

tvs6 asked in Theory of Computation Dec 30, 2020

by tvs6

5 points

61 views

0 votes

2 answers 61 views

TOC- closure properties of RL
let L1=a^n (which is a regular language) and L2=b^n (which is also a regular language) L1.L2 is also regular.. how?? as (a^nb^n) is not a regular language

Updesh Singh asked in Theory of Computation Dec 26, 2020

by Updesh Singh

9 points

61 views

0 votes

1 answer 53 views

Theory of automata
Convert the Following DFA to Regular Expression using GNFA.

M.hamza asked in Theory of Computation Dec 26, 2020

5 points

53 views

0 votes

0 answers 15 views

Introduction to Languages and The Theory of Computation

aryan1234 asked in Theory of Computation Dec 23, 2020

5 points

15 views

0 votes

0 answers 16 views

Introduction to Languages and The Theory of Computation John C. Martin North Dakota State University

aryan1234 asked in Theory of Computation Dec 23, 2020

5 points

16 views

0 votes

0 answers 12 views

Introduction to Languages and The Theory of Computation John C. Martin

aryan1234 asked in Theory of Computation Dec 23, 2020

5 points

12 views

0 votes

1 answer 33 views

#selfdoubt #regular_toc_languages

gajendercse asked in Theory of Computation Dec 21, 2020

41 points

33 views

Page:

Search GATE CSE Doubts