Recent questions and answers in Theory of Computation

0 votes

1 answer 5 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?

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?

answered 1 day ago in Theory of Computation asqwer 633 points 5 views

0 votes

1 answer 19 views

Describe the language corresponding to following (1+01)*(0+01)*

This question appeared in my b.tech university exam 2021. This question is of 2 marks. As, i’m preparing side by side for gate exam too so anyone can help me in this question ?

answered Jul 26 in Theory of Computation asqwer 633 points 19 views

0 votes

1 answer 14 views

A={ww^rw^rw|w belong to £*} is CFL or not
Any one can solve this question please give brief explanation for this question

Any one can solve this question please give brief explanation for this question

answered Jul 22 in Theory of Computation asqwer 633 points 14 views

0 votes

1 answer 15 views

pumping lemma
@Praveen Saini @Lakshman Patel RJIT @Digvijay Pandey Just wanted to ask doubt, If the minimum pumping length of the language can be 0 for any language? I think it should not be as any string will either be accepted or rejected.

@Praveen Saini @Lakshman Patel RJIT @Digvijay Pandey Just wanted to ask doubt, If the minimum pumping length of the language can be 0 for any language? I think it should not be as any string will either be accepted or rejected.

answered Jul 14 in Theory of Computation asqwer 633 points 15 views

0 votes

1 answer 16 views

#SELF_DOUBT_FROM_RICE_THEOREM
If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM

If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM

answered Jul 13 in Theory of Computation asqwer 633 points 16 views

0 votes

1 answer 29 views

Self doubt.
What are the differences between a dead state and a trap state?

What are the differences between a dead state and a trap state?

answered Jul 10 in Theory of Computation asqwer 633 points 29 views

0 votes

1 answer 14 views

An introduction to formal languges
Construct Turing machines that will accept the following languages on {a, b}. L= {w|w| is even}.

Construct Turing machines that will accept the following languages on {a, b}. L= {w|w| is even}.

answered Jul 10 in Theory of Computation asqwer 633 points 14 views

0 votes

1 answer 40 views

Theory of computation Dpda
Can anyone make Dpda for the following languages L1={ a^nb^m| n>m;n,m>0} L2= { x ∈ { a, b }* | na (x) > nb (x) } I have find too little solution and but everyone violating Dpda definition like for any q€Q ,x€ T( stack symbol ) if, ∆(q, epsilon,x) !=phi then ∆(q,a,x)= phi for every a€sigma Please anyone help...

Can anyone make Dpda for the following languages L1={ a^nb^m| n>m;n,m>0} L2= { x ∈ { a, b }* | na (x) > nb (x) } I have find too little solution and but everyone violating Dpda definition like for any q€Q ,x€ T( stack symbol ) if, ∆(q, epsilon,x) !=phi then ∆(q,a,x)= phi for every a€sigma Please anyone help...

answered Jul 6 in Theory of Computation asqwer 633 points 40 views

0 votes

0 answers 7 views

Simple explanation of decidable, undecidable, recognizable and unrecognizable

Hello everyone, I am bit confused with the terms decidable, undecidable, recognizable and unrecognizable. For example for L1 I thought its decidable because the Turing machine can find word which can have a lenght of 2020. But its not the case its undecidable. I tried to ... problem so I reduce the L1 to ATM if the language is in L1 then accepts otherwise it loops forever. Thanks for your answer!

asked Jun 26 in Theory of Computation sayuri 5 points 7 views

0 votes

0 answers 9 views

MadeEasy TOC question
hi, this is MadeEasy TOC question. It mentions to eliminate X first and then Y. How can this be done, I mean how can we eliminate X and Y since even after subsitution they will be repeating. I know here we have to use arden’s theorem but unable to understand how to reduce. Please help…....….

hi, this is MadeEasy TOC question. It mentions to eliminate X first and then Y. How can this be done, I mean how can we eliminate X and Y since even after subsitution they will be repeating. I know here we have to use arden’s theorem but unable to understand how to reduce. Please help…....….

asked Jun 25 in Theory of Computation rish1602 9 points 9 views

1 vote

1 answer 714 views

GATE CSE 2021 Set 1 | Question: 1 | Video Solution

Suppose that $L_1$ is a regular language and $L_2$ is a context-free language. Which one of the following languages is $\text{NOT}$ necessarily context-free? $L_1 \cap L_2$ $L_1 \cdot L_2$ $L_1- L_2$ $L_1\cup L_2$

answered Jun 24 in Theory of Computation amitkhurana512 173 points 714 views

3 votes

1 answer 831 views

GATE CSE 2021 Set 1 | Question: 12 | Video Solution

Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is ... $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$

answered Jun 18 in Theory of Computation amitkhurana512 173 points 831 views

0 votes

0 answers 14 views

Clear distinction between Finite automata, Regular expressions

Given language L = strings starting with 'a'. Sigma(Alphabet) = {a,b} DFA: It should only accept the given language and reject other languages. Therefore only strings starting with 'a' MUST be accepted by the DFA, and the strings starting with 'b' MUST ... and Regular expressions are not correctly defined by me, can you please define all these clearly so that it becomes easy to distinguish them.

asked Jun 12 in Theory of Computation akshansh 15 points 14 views

0 votes

0 answers 12 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)* ?

How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?

asked Jun 9 in Theory of Computation hrtoimukra 5 points 12 views

0 votes

0 answers 20 views

can we make DFA for a language where there is comparion between symbols but lanuage is finite a^nb^n;n<=3

asked Jun 8 in Theory of Computation promise 5 points 20 views

0 votes

0 answers 19 views

if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??

asked Jun 8 in Theory of Computation promise 5 points 19 views

0 votes

0 answers 9 views

#Ullman #RegularLanguage
It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?

It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?

asked May 29 in Theory of Computation Palash Nandi 1 13 points 9 views

0 votes

0 answers 7 views

#Ullman #Homomorphism
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?

Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?

asked May 29 in Theory of Computation Palash Nandi 1 13 points 7 views

1 vote

1 answer 12 views

#Ullman #RegularLanguage
Please Correct me if Logic is wrong. Let w = w1.w2.w3...wk, By definition of min(L), w ∈ L but any w1.w2.w3...w(k-1) doesn’t. Then NO prefix reach any final state regardless of their length. Using only prefixes of w drawing a dfa is not possible but w itself belongs to L and min(L). So dfa of min(L) exists.=> Closed.

Please Correct me if Logic is wrong. Let w = w1.w2.w3...wk, By definition of min(L), w ∈ L but any w1.w2.w3...w(k-1) doesn’t. Then NO prefix reach any final state regardless of their length. Using only prefixes of w drawing a dfa is not possible but w itself belongs to L and min(L). So dfa of min(L) exists.=> Closed.

answered May 29 in Theory of Computation Deepakk Poonia (Dee) 1.7k points 12 views

0 votes

0 answers 8 views

#Ullman #TOC #RegularLanguage
Check if max(L) is closed or not for max(L) : { w| w is in L but no x other than EmptyString, wx is in L }. Correct if Logic is wrong., If wx is not in L ( except x is empty ) i.e. x forces the flow to stop at a non-Final state. So unless x is ... on a final state, so is w alone. A dfa is possible for all w' in L => dfa is possible for w' for max(L) => Closed.

Check if max(L) is closed or not for max(L) : { w| w is in L but no x other than EmptyString, wx is in L }. Correct if Logic is wrong., If wx is not in L ( except x is empty ) i.e. x forces the flow to stop at a non-Final state. So unless x is Empty, constructing a ... wx lands on a final state, so is w alone. A dfa is possible for all w' in L => dfa is possible for w' for max(L) => Closed.

asked May 29 in Theory of Computation Palash Nandi 1 13 points 8 views

0 votes

0 answers 7 views

#Ullman #RegularLanguage
check if init(L) is closed or not where init(L) = { w | for some x, wx is in L } => Correct if Logic is wrong. Let there are n differnt state in dfa of L. Case_1: if len( wx ) >= n and wx is in L then x is either EmptyString or ... is EmptyString else whether single w' reach the final state is undecidable. So., x is Empty for sure, for all w in init(L) => Closed.

check if init(L) is closed or not where init(L) = { w | for some x, wx is in L } => Correct if Logic is wrong. Let there are n differnt state in dfa of L. Case_1: if len( wx ) >= n and wx is in L then x is either EmptyString or a loop. So deleting ... then either x is EmptyString else whether single w' reach the final state is undecidable. So., x is Empty for sure, for all w in init(L) => Closed.

asked May 29 in Theory of Computation Palash Nandi 1 13 points 7 views

0 votes

0 answers 8 views

#Ullman #Homorphism
Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?

Exercise 4.2.1.(f) Suppose h is the homomorphism from the alphabet { 0, 1, 2 } to the alphabet { a, b } defined by h(0) = a, h(1) = ab, h(ba) = ba. If L = { a(ba)* } then What is the language created by inverse_h(L) ?

asked May 27 in Theory of Computation Palash Nandi 1 13 points 8 views

1 vote

1 answer 14 views

Self Doubt : Push Down Automata
In place of highlighted transition can we use the below transitions: epsilon,a|a , epsilon,b|b , epsilon,z0|z0 ?

In place of highlighted transition can we use the below transitions: epsilon,a|a , epsilon,b|b , epsilon,z0|z0 ?

answered May 24 in Theory of Computation Deepakk Poonia (Dee) 1.7k points 14 views

0 votes

1 answer 15 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 ?

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 ?

answered May 19 in Theory of Computation Kanwae Kan 5 points 15 views

0 votes

1 answer 17 views

wxw^ry | w,x,y in {a,b}* is regular or not ? self doubt

answered May 19 in Theory of Computation Kanwae Kan 5 points 17 views

0 votes

1 answer 18 views

while making compound automata do we have to include the dead states too in the cartesian product ?[self doubt]

while making compound automata do we have to include the dead states too in the cartesian product ? or can we ignore the dead states and then make the compound automata?

answered May 18 in Theory of Computation aryavart 73 points 18 views

0 votes

0 answers 22 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.

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.

asked May 16 in Theory of Computation rythmrana 5 points 22 views

1 vote

0 answers 27 views

Theory of computation - Pumping Lemma for CFL [Self Doubt]

The language is : number of zeroes=number of ones(which can be done by a deterministic Push down automata) say w=11101000 now we divide it to 5 parts u,v,w,x,y , where u=1 v=110 w=1 x=00 y=0 L=u.(v*i).w.(x*i).y such that i>=0 but when we put i=0 the ... . This shows that the language is not in L . But as the language can be done by a PDA , it should not have failed ,or do i not understand it ?

asked May 12 in Theory of Computation hari0943 9 points 27 views

0 votes

0 answers 15 views

Design Turing Machine for LANGUAGE L1=a*bb(a+b)*

asked May 6 in Theory of Computation chris gyle 5 points 15 views

1 vote

0 answers 16 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.

Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.

asked May 3 in Theory of Computation Setsu 13 points 16 views

1 vote

0 answers 12 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. [closed]

Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.

asked May 3 in Theory of Computation Setsu 13 points 12 views

0 votes

0 answers 21 views

PhD Admissions Written Test (Basic)
For any language L, and for any k ≥ 0, let L k denote the language obtained by concatenating any k strings from L (note that L^0 = epsilon). Suppose L1 is a context-free language and R is a regular language over the same alphabet Σ of size at least 3. The smallest value of k for which (R \ L1) k ∪ (L1 \ R) is not necessarily context-free is

For any language L, and for any k ≥ 0, let L k denote the language obtained by concatenating any k strings from L (note that L^0 = epsilon). Suppose L1 is a context-free language and R is a regular language over the same alphabet Σ of size at least 3. The smallest value of k for which (R \ L1) k ∪ (L1 \ R) is not necessarily context-free is

asked May 2 in Theory of Computation Rashimdixit 9 points 21 views

0 votes

0 answers 14 views

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

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

asked May 2 in Theory of Computation Gogo6996 5 points 14 views

0 votes

0 answers 12 views

Ambiguity in grammar
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

asked May 2 in Theory of Computation Sravanth0989 5 points 12 views

0 votes

0 answers 10 views

Ambiguity of grammar
Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

Show that the following grammar is ambiguous. S → aB|ab, A → aAB|a, B → ABb|b.

asked May 2 in Theory of Computation Sravanth0989 5 points 10 views

0 votes

0 answers 11 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}????

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 harshit_1010 5 points 11 views

0 votes

0 answers 39 views

madeeasys toc workbook
can somebody explain how to solve this type of questions

can somebody explain how to solve this type of questions

asked Apr 26 in Theory of Computation jainanmol123 13 points 39 views

0 votes

1 answer 36 views

Book: Introduction to formal languages and automata by Peter Linz----Chapter 2: Finite Automata----Exercises

Construct a DFA for input alphabet {a,b} with EXACTLY 2 a’s & MORE THAN 2 b’s. (Note: Order is NOT specified in the question.)

answered Apr 21 in Theory of Computation Konan-kun 71 points 36 views

0 votes

0 answers 19 views

#DFA Introduction, Formal Languages, DFA Construction examples

asked Apr 10 in Theory of Computation DarkShadow18 5 points 19 views

0 votes

0 answers 27 views

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

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

asked Apr 7 in Theory of Computation shri385 5 points 27 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

Log In

Register

Recent Posts

No Recent Blog Comments

Recent questions and answers in Theory of Computation