Recent questions tagged toc-languages - GATE CSE Doubts

+1 vote

0 answers

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.

asked May 3 in Theory of Computation by Setsu (13 points) | 9 views

+1 vote

0 answers

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.

asked May 3 in Theory of Computation by Setsu (13 points) | 6 views

0 votes

0 answers

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

asked May 2 in Theory of Computation by Gogo6996 (5 points) | 5 views

0 votes

0 answers

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}????

asked May 2 in Theory of Computation by harshit_1010 (5 points) | 3 views

0 votes

0 answers

#DFA Introduction, Formal Languages, DFA Construction examples

asked Apr 10 in Theory of Computation by DarkShadow18 (5 points) | 18 views

0 votes

0 answers

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

asked Apr 7 in Theory of Computation by shri385 (5 points) | 16 views

0 votes

0 answers

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

asked Mar 4 in Theory of Computation by jaswanth431 (5 points) | 20 views

+2 votes

1 answer

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

asked Mar 4 in Theory of Computation by samir757 (17 points) | 30 views

0 votes

1 answer

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?

asked Feb 6 in Theory of Computation by shantanu4raje (25 points) | 44 views

0 votes

0 answers

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

asked Feb 3 in Theory of Computation by rahul65 (5 points) | 25 views

0 votes

0 answers

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

asked Feb 2 in Theory of Computation by kirtipurohit (15 points) | 39 views

0 votes

0 answers

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?

asked Feb 1 in Theory of Computation by RavGopal (145 points) | 32 views

0 votes

0 answers

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

asked Feb 1 in Theory of Computation by Abhineet Singh (23 points) | 31 views

+1 vote

0 answers

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

asked Jan 29 in Theory of Computation by aditi19 (53 points) | 36 views

0 votes

0 answers

Madeeasy Test series TOC Q1

asked Jan 23 in Theory of Computation by Shivateja MST (45 points) | 22 views

0 votes

0 answers

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

asked Jan 18 in Theory of Computation by kirtipurohit (15 points) | 10 views

0 votes

1 answer

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

asked Jan 18 in Theory of Computation by kirtipurohit (15 points) | 21 views

0 votes

0 answers

An introduction to formal languages and automata peter linz

asked Jan 16 in Theory of Computation by kirtipurohit (15 points) | 45 views

0 votes

0 answers

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$ }

asked Jan 14 in Theory of Computation by aditi19 (53 points) | 13 views

+1 vote

0 answers

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$ }

asked Jan 14 in Theory of Computation by aditi19 (53 points) | 32 views

0 votes

1 answer

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

asked Jan 4 in Theory of Computation by Nitinkumar.097 (13 points) | 29 views

0 votes

0 answers

GATE 2003 , Theory Of Computation , Turing Machine

asked Jan 4 in Theory of Computation by Pushkar Khadase (5 points) | 31 views

0 votes

3 answers

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

asked Dec 30, 2020 in Theory of Computation by tvs6 (5 points) | 48 views

0 votes

2 answers

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

asked Dec 26, 2020 in Theory of Computation by Updesh Singh (9 points) | 52 views

0 votes

1 answer

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

asked Dec 26, 2020 in Theory of Computation by M.hamza (5 points) | 46 views

0 votes

0 answers

Introduction to Languages and The Theory of Computation

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 8 views

0 votes

0 answers

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

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 10 views

0 votes

0 answers

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

asked Dec 23, 2020 in Theory of Computation by aryan1234 (5 points) | 9 views

0 votes

1 answer

#selfdoubt #regular_toc_languages

asked Dec 21, 2020 in Theory of Computation by gajendercse (41 points) | 30 views

0 votes

1 answer

theory of computation
Can some one identify what is the language&PDA for this CFG & is it DCFL / NCFL ? E->E+E E->E*E E->id

asked Dec 14, 2020 in Theory of Computation by vrajdobariya (9 points) | 25 views

+1 vote

1 answer

NLCIL2020(basic)
Q.1) which of the following represent $ab^{*}+b^{*}$ a)starting with “a” and followed by “b”. b)having “a”s but not “b”s. c)having no “a”s but only “b”s. d)b starting with an a having no other “a”s or “a”s but only “b”s.

asked Nov 30, 2020 in Theory of Computation by BASANT KUMAR (25 points) | 33 views

0 votes

0 answers

Self Doubt: TOC Languages
Say I am given an arbitrary language – a set of words. Is there any standard way to determine if the set of words is Regular or Context-Free or Recursive or Recursively Enumerable

asked Nov 25, 2020 in Theory of Computation by swaroop-nath (5 points) | 26 views

0 votes

1 answer

Introduction to automata Peter Linz 6th edition Exercise 1.2

asked Nov 25, 2020 in Theory of Computation by Sohil Bhanani (5 points) | 58 views

0 votes

0 answers

applied gate
Q.25)Max Marks: 2Subject: Theory of Computation A B C Correct Option Solution: (C) D None of these Your answer is Wrong

asked Nov 23, 2020 in Theory of Computation by Mayur Rasadiya (5 points) | 22 views

0 votes

0 answers

applied gate
Q.1)Max Marks: 1Subject: Theory of Computation Suppose that L is context free and R is regular. Consider the following statements I. Is L - R necessarily context free II. Is R - L necessarily context free A I is True Correct Option Solution: (A)

asked Nov 22, 2020 in Theory of Computation by Mayur Rasadiya (5 points) | 18 views

0 votes

0 answers

applied gate
Q.2)Max Marks: 1Subject: Theory of Computation A Regular but not context free B Not Regular but Context free Correct Option | Attempted Solution: (B) C Neither Regular nor Context free D Regular and Context free

asked Nov 22, 2020 in Theory of Computation by Mayur Rasadiya (5 points) | 15 views

0 votes

1 answer

Just thinking about it
Since Reduce entries in both LR(0) and SLR(1) are different. so does that mean error entries will also be different in these two.

asked Nov 22, 2020 in Compiler Design by amanizardar (5 points) | 23 views

+1 vote

1 answer

ACE Academy Booklet

asked Nov 12, 2020 in Theory of Computation by Vishal_kumar98 (37 points) | 41 views

+1 vote

1 answer

ACE Academy Booklet

asked Nov 9, 2020 in Theory of Computation by Vishal_kumar98 (37 points) | 24 views

0 votes

2 answers

miscellaneous
in this question GATE2008-9 Which of the following is true for the language {a^p∣p is a prime }? It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine why is it not regular … as in we can for NFA for it?

asked Nov 2, 2020 in Theory of Computation by rish1602 (9 points) | 51 views

Page:

9,270 questions

3,204 answers

14,751 comments

96,304 users