# Tagged Questions

Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

60 views

### If $A$ is regular, is the language $\{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$ regular?

Here is the question: Let $A$ be any regular set over some alphabet $\Sigma$. Is the language $$L = \{x \;\mid\; \exists y : |y| = |x|^2, xy \in A\}$$ necessarily regular? I am unable to ...
44 views

### what is the complement of the language L={ww : w ∈{a,b}* }

The given language is not CFL ,it is CSL and CFL is not closed under complement operation ,Now I am not getting how to find it's complement ,please tell the approach .
62 views

### Converting Automata To Regular Expression Using State Removal Method

From the following automaton this solution is given: $$(a\mid b)^*aa(ba)^*a(a\mid b)^*$$ But when I try to convert this automaton into a regular expression I always end up with the wrong ...
71 views

### what is the complement of empty language?

If R- Regular language , C-Context Free language and L -Recursive language then what is the result of the expression ((R-C)-L)',Now first starting with R-C , It will give result as ∅, since every ...
73 views

### Understanding Turing Machines: Recognizable and Decidable langauges

I've searched tons of resources and while conceptually I understand the turing machine itself and what it does- I'm a bit stuck on Turing Recognizable and Turing Decidable languages and I'm not sure ...
45 views

### Acceptance by final state PDA and acceptance by empty stack .

Let $P$ be a non-deterministic push-down automaton (NPDA) with exactly one state, $q$, and exactly one symbol, $Z$, in its stack alphabet. State $q$ is both the starting as well as the accepting state ...
33 views

### Trying to figure what language this PDA (pushdown automata) accepts

I have the following PDA and I can't figure our what words it accepts, would like to get some help with figuring this out. Of course it only accepts if that stack is empty in the accepting state.
31 views

36 views

### Prove about $NFA$ and pumping lemma

The question: Let it be $L$ a regular language. few definitions: $p(L)$-the minimum natural number so that $L$ fulfills the pumping lemma. $n(L)$- minimal NFA that accepts $L$. $m(L)$- $Rank(L)$, the ...
27 views

### Regular Pumping Lemma

\begin{align*} L&=\left\{b^5w:w\in\{a,b\}^*,\big(2n_a(w)+5n_b(w)\big)\bmod 3=0\right\}\\ L&=\left\{(ab)^na^k:n>k,k\ge 0\right\} \end{align*} Determine if each language is regular or ...
40 views

### which of the following languages are regular?

If w,x,y ∈ (a+b)^+ 1)L=wxwy 2)L=xwyw 3)L=wxyw According to me all of them should be non-regular since we can't actually check what will be the starting symbol of first occurrence of w since it ...
25 views

26 views

### Designing a DFA to accept a string

I have created the following FA Im i correct?
60 views

### Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be invalid....
40 views

38 views

### Minimization of DFA

I have the following question I have minimized the DFA as the following since the states can only be partitioned to [S0][S1 S2] EDIT: Is my Minimization correct?
17 views

### Deterministic FSM accepting a binary string whose number of zero is either multiple of 2, 3, or both

I can build a FSM that accept binary string with multiple of 2 number of 0, and I can also build a FSM that accept binary string with multiple of 3 number of 0, but I cannot figure out how I can ...
50 views

### Using the Pumping Lemma to show that the language of all strings of even length having no $0s$ in their second half is not regular

I'm struggling with finding a starting string $s$ to prove using the Pumping Lemma that language $$L = \{w \mid w\text{ has even length and the second half of w does not contain any 0s}\}$$ is ...
25 views

### Finite automata dfa/nfa language problem review

I have completed the questions below but am not sure if they are correct. If anyone could help me confirm them it would be much appreciated. 3) This took me a little while but it seems to hold up. Im ...
52 views

### Panalphebetic strings provable by DFA?

Is the language of panalphabetic strings decidable by DFA? If so, how can I prove it? A string {a,…,z}* is said to be panalphabetic if it contains at least one occurrence of each letter.
29 views

### Pumping lemma for context free. How do I define the string 'w' and define cases?

I am new to the pumping lemma for context free grammars. I have read books and researched online about the pumping lemma, however I am finding it difficult to understand the actual concept and how to ...
17 views

### NFA Containing 'a'

I have L={Contains 'a'} and Alphabet(E)={a,b} Can i create a NFA Like this
30 views

### Wrong prove for $L=\{a^m:m\geq 0,\; m \mod 3\neq 0\}$ isn't regular, but why?

First, let me just say that this language is regular, and I understand why. But before I understood that, I tried proving that L isn't regular with pumping lemma. I just can't figure what is wrong ...
20 views

### Checking if $L_1 \cup L_2$ is regular language

Let $L_1=\{a^n b^r|n \geq 1, r\geq1,n=r\}$ $L_2=\{a^n b^r|n \geq 1, r\geq1,n\neq r\}$ be a non regular languages $L_1 \cup L_2$ is regular? I think that $L_1 \cup L_2$ is regular because we ...
81 views

### Let M range over turing machine descriptions .Consider the set REG={M|L(M) is a regular set} which of the statements are true?

The complement of REG is Co-REG REG is recursively enumerable but Co-REG is not REG is not recursively enumerable but Co-REG is Both are recursively enumerable 4.None of them are recursively ...
74 views

### How to prove that $L=${$a^p$: p is prime} isn't regular?

I tried using pumping lemma or finding infinite equivalence classes, but I didn't succeed. It's clear to me that there is no automata that accepts this language, but I just can't formally prove that ...
219 views

### Prove that $wu=uw$, given that $w^5=u^3$

Suppose $w,u\in\Sigma^*$, $w^5=u^3$, and I need to show that $wu=uw$. I started with $5|w|=3|u|$, but I didn't know how to continue... any suggestions?
Consider the following subsets of $\{ a, b, \$ \} ^*$:$A = \{ xy \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$and$B = \{ x \$y \mid x,y \in \{ a, b, \} ^*, \#a(x) = \#b(y) \}$. Which of the ...