# Tagged Questions

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

422 views

### Showing that two regular expressions represent complementary regular languages over {0,1}

How do up you show that two that the regular expressions, such as $(01+1)^*$ and $(0+1)^*\left(0 + 00(0+1)^*\right)$ represent complementary regular languages over $\{0,1\}$? I'm trying to do some ...
74 views

### Closure property of Alternating language

Problem Given a language $L$ is context-free, must $\operatorname{alt}(L)$ is also context free? where $$\operatorname{alt}(L) = a_1a_2a_3 \ldots, \quad L = a_1b_1a_2b_2a_3b_3 \ldots$$ I couldn't ...
292 views

### Question regarding the initial stack symbol in Push Down Automaton

Let $L = \{a^nb^n : n \geq 0\} \cup \{a\}$, where $\Gamma = x, \$, \Sigma = {a, b}$, we have the NPDA of$L$in three states: In the above state diagram, I can break the transtion$\lambda, \lambda ...
47 views

### FSM to add two integer

Design a Mealy machine to add two integer(binary number). I can not determine how to deal with the carry.And what to do with the last carry generated.
23 views

### Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$

Consider the language $L_1=\{a^pb^qc^r \mid p,q,r>0\}$ and $L_2=\{a^pb^qc^r \mid p,q,r\geq0 \space\text{and}\space p=r\}$, then which of the following statements are true? $L_1\cup L_2$ is a ...
29 views

### relation on Languages of one finite machine !?

I adopted this question from 2013 Final Entrance Exam on CS. We have Finite Machine $M$ and Languages $L_1$ to $L_4$ as depicted in following picture: The question is which of the $A$ to $D$ ...
71 views

### Is the language of complex numbers regular?

A complex number is a number that can be expressed in the form $a + bi$, where $a$ and $b$ are real numbers and i is the imaginary unit, that satisfies the equation $i^2 = −1$. In this expression, $a$ ...
37 views

21 views

### What is the Right Context of a Word in Formal Langauge Theory?

I am reading this paper and am unable to understand this notation in section 2.2 - The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The ...
40 views

### Proving that reguarity is closed under prefixes?

Show that regularity is closed under prefixes. That is, if $L$ is regular, then so is $$L_1 = \{x \mid \exists y: xy\in L\}$$ I am having a hard time trying to work this through. Can you please ...
28 views

### How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
47 views

### Proving that the given language is non regular

We had a question today as follows: Let $L$ be a nonregular language and $X$ a finite set of strings from the same alphabet as $L$. (a) Prove that $L ∪ X$ is nonregular. (b) Prove that $L - X$ is ...
27 views

Claim: Let $L \subseteq \Sigma^*\{\#\}\Sigma^*$ be a context-free language, where $\# \notin \Sigma$. Suppose that for each $x \in \Sigma^*$, $\{y|x\#y \in L\}$ is finite. Then $\{y|\text{ for some } ... 1answer 24 views ### Parser for reversed language Language$L$is specyfied by grammar :$(\{S,A,B\},\{c,d\},S,\{S \rightarrow SA, A \rightarrow Bc | \epsilon, B \rightarrow d\})$. My task is to construct LR(1) parsing table for language$L^R$(with,... 1answer 50 views ### Synchronizing sequence From Sipser's book: Let$M=(Q,\Sigma,\delta,q_0,A)$be a DFA and let$h$be a state of$M$called its "home". A synchronizing sequence for$M$and$h$is a string$s\in \Sigma^*$where$\delta (q,...
Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...