# Recent questions and answers in Theory of Computation

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?
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 ?
Any one can solve this question please give brief explanation for this question
@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.
If a language satisfies monotonic property then is it REL or REC or NOT REL ?? And What about CO- REL?? #RICE THEOREM
What are the differences between a dead state and a trap state?
Construct Turing machines that will accept the following languages on {a, b}. L= {w|w| is even}.
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...
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!
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…....….
1 vote
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$
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 ^* \}$
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.
How is the regular expression (0+1)*0(0+1)*1(0+1)* is equivalent to (0+1)*01(0+1)* ?
can we make DFA for a language where there is comparion between symbols but lanuage is finite a^nb^n;n<=3
if language is finite then dfa possible irrespective of comparison between symbols exist or not.is it true??
It is clear than alt(L,M) is L = {(ab)+}. So dfa is possible but How to prove it formally?
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) ?
1 vote
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.
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.
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.
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) ?
1 vote
In place of highlighted transition can we use the below transitions: epsilon,a|a , epsilon,b|b , epsilon,z0|z0 ?
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 ?
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?
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.
1 vote
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 ?
1 vote
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.
1 vote
Construct a left-linear grammar for the language S→ abA A → baB B → aA | bb.
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
Levi Ackerman: Is L= {xwywr∣x, w,y∈(a+b) +} regular? wr is reverse of w
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.