Register

Web Page

Regular expressions and finite automata, Context-free grammars and push-down automata, Regular and context-free languages, Pumping lemma, Turing machines and undecidability.

$$\scriptsize{\overset{{\large{\textbf{Mark Distribution in Previous GATE}}}}{\begin{array}{|c|c|c|c|c|c|c|c|}\hline
\textbf{Year}&\textbf{2024-1} & \textbf{2024-2} & \textbf{2023} & \textbf{2022} & \textbf{2021-1}&\textbf{2021-2}&\textbf{Minimum}&\textbf{Average}&\textbf{Maximum}
\\\hline\textbf{1 Mark Count} &1&1&3& 2 &2&3& 1&2&3
\\\hline\textbf{2 Marks Count} &2&3&3& 3 &3&4& 2&3&4
\\\hline\textbf{Total Marks} &5&7&9& 8 &8&11&\bf{5}&\bf{8}&\bf{11}\\\hline
\end{array}}}$$

Filter

Recent questions in Theory of Computation

#4441
430
views
0 answers
0 votes
http://www.cs.rice.edu/~nakhleh/COMP481/
Can anybody please explain this reduction and rice theorem.http://www.cs.rice.edu/~nakhleh/COMP481/Thanks
User Avatar
#4442
508
views
2 answers
0 votes
closure property of cfl
Can complement of a non-regular language be regular?
User Avatar
#4443
552
views
1 answers
0 votes
Digital Electronics
Size of rom for converting binary code to gray code?
User Avatar
#4444
1.3k
views
2 answers
0 votes
regular expression
write the regular expression for the given language L= { W | NO OF a mod 2= 1} (odd no of a's )
User Avatar
#4445
512
views
1 answers
0 votes
Doubt
can language wcwR accepted by a single queue?i want someone to parseabcRcba using a QUEUE
User Avatar
#4446
592
views
3 answers
0 votes
Regular Expression
Given statement is true or false 1. L is regular language $\Leftrightarrow$ Ǝ a regular expression without $\bigstar$ answer in detail
User Avatar
#4447
2.7k
views
3 answers
2 votes
Theory proof
1. The complement of a finite language is always infinite2. The complement of an infinite language may be finite or infinite ..both statements are true .. i can proof using examples .. can someone give me logical theory proof ?
User Avatar
#4448
421
views
1 answers
0 votes
Test by Bikram | Mock GATE | Test 4 | Question: 53
Which of the following languages over the alphabet set $\{ a, b \}$ is described by the regular expression$a^\ast b$(aa)$^\ast b$ ?The set of all strings ... of all strings ending with $ b'$.The set of all strings having sub sequence $bb$.
User Avatar
#4449
230
views
1 answers
1 votes
Test by Bikram | Mock GATE | Test 4 | Question: 44
Which of the following regular expressions describes the same set of strings as $\left ( a^*+b \right )^*$ $\left ( c+d \right )$ ... $a^{\ast }\left ( c+d \right )+ b^{\ast }\left ( c+d \right )$
User Avatar
#4450
521
views
0 answers
2 votes
Test by Bikram | Mock GATE | Test 4 | Question: 35
Let $DM$ be a single-tape, Deterministic Turing machine with tape alphabet $\left \{ blank,0,1 \right \}$, and let $C_i$ denote the (possibly infinite) ... during the computation $C_i.$III onlyI and III onlyII and III onlyI, II, and III
User Avatar
#4451
748
views
1 answers
4 votes
Test by Bikram | Mock GATE | Test 4 | Question: 26
Consider the languages $A$ and $B$, each over the alphabet set $\left \{ a,b \right \}$.Here, $B=\{ w \mid w$ contains some $x \in A$ as a sub-string $\}.$ ... $B$ is context-free. II only II and III I and III only I, II and III
User Avatar
#4452
489
views
2 answers
0 votes
Test by Bikram | Mock GATE | Test 4 | Question: 23
The definition of a language $N$ with alphabet set $\left \{ x \right \}$ ... }$ to recognize $N$ is _________.$p+m$p+1$m+1$2^\left ( p+1 \right )$
User Avatar
#4453
420
views
1 answers
2 votes
Test by Bikram | Mock GATE | Test 4 | Question: 9
If $L$ is the set of all strings over $\{ x,y\}$ containing at least one $x$, then which of the following regular expressions does not generate $L$?$(x+y)^* x(y+y)^*$y^*x ( x+y)^*$( x+y)^* x$( x+y)^* xy^*$
User Avatar
#4454
997
views
1 answers
0 votes
Peter Linz Exercise 11.1
If L is recursive, is it necessarily true that L+ is also recursive?
User Avatar
#4455
269
views
0 answers
0 votes
Peter Linz Exercise 11.1
Prove that the complement of context free language is recursive.
User Avatar
#4456
465
views
2 answers
1 votes
Toc question
Consider the two given languages :A={x:x is an integer and divisible by 2) B ={2x:x is an integer }.Which of the following is correct?A) A is accepted ... not by AC) Both A and B are accepted by an automataD)None are accepted by automata
User Avatar
#4457
1.1k
views
3 answers
0 votes
TOC QUESTION
Which of the following is not true?A)Class of All languages is not countableB)Every language in P is also in NPC)Every language in NP is decidabale.D)There are some languages in NP but not in P
User Avatar
#4458
3.3k
views
3 answers
2 votes
CSL and Regular language
if L1 = { anbncn | n>= 0 } and L2 = { anbmck | k,n,m>=0}L1 is CSL and L2 is regular.Now L3 = L1.(L2)*.Is L3 is regualar or CSL?
User Avatar
#4459
6.9k
views
2 answers
5 votes
ISRO2017-77
If $L$ and $P$ are two recursively enumerable languages then they are not closed underKleene star $L^*$ of $L$Intersection $L \cap P$Union $L \cup P$Set difference
User Avatar
#4460
2.0k
views
3 answers
3 votes
Minimization of DFA
DFA for Every 'a' followed by 'b'. The second one is correct but I want to know if the first one is correct or not? If not please share an example.
User Avatar
Page: