Forem: Hani

An Overview of Turing Machines

Hani — Fri, 10 Jan 2020 19:25:06 +0000

The famous mathematician Alan Turing introduced the abstract concept of a Turing machine as a part of his research on a problem that was introduced in 1928 by David Hilbert called Entscheidungsproblem. The importance of Turing machines arises because they're one of the first theoretical models for computers and, consequently, a number of theories and ideas in the computer science field were based on this concept. In this post, I'm going to walk you through Turing Machines' concept.

There are multiple versions of Turing machines, but the most popular and intuitive one is the standard Turing machine (STM). Throughout this post, the STM will be used.

Informal Definition
Formal Definition
Transitions
Language acceptors VS. transducers
Example

Informal Definition

Turing machine has a tape which is infinite from both sides of the input. The following picture visualizes the tape of the input aabbcc:

Cells on each side of the input are empty (i.e. blanks) and denoted by the symbol □.

There's a scanner that scans the cell content and performs the next action based on the scanned input. The next action can be writing in the current cell and then moving left/right. In the initial configuration of the Turing machine, the scanner is set to the leftmost character of the input as the following picture shows:

A Turing machine accepts strings that halt in a final state which merely depends on the scanner (which has a kind of a Finite automaton). Therefore, we can conclude that the tape contents are irrelevant to the acceptance of strings.

A Turing machine rejects strings that halt in a non-final states or don't halt at all. In the latter case, the Turing machine runs into an infinite loop because of the input string.

Formal Definition

The formal definition is easier to understand when it's read simultaneously with a real example. If you feel that you are unable to digest the definition, take a look at the example provided in Example section.

A Turing machine M is defined by
M = (Q,Σ,Γ,δ,q0, ,F) where
Q is the set of internal states,
Σ is the input alphabet
Γ is the finite set of symbols called the tape alphabet,
δ is the transition function,
□ ∈ Γ is a special symbol called the blank,
q0 ∈ Q is the initial state,
F ⊆ Q is the set of final states.

In the definition of a Turing machine, we assume that Σ ⊆ Γ – {□}, that is, that the input alphabet is a subset of the tape alphabet, not including the blank. Blanks are ruled out as input for reasons that will become apparent shortly. The transition function δ is defined as δ : Q × Γ → Q × Γ × {L,R}.

Transitions

δ(q, a) = (q0, b,R) means that from state q, if you see a on tape, go to state q0, write b on tape, and move one square to the right on the tape.

δ(q, a) = (q0, b, L) means same as above, except move left on the tape.

What if δ(q, a) is undefined ? (i.e. δ(q, a) = Φ, there is no move corresponds to the pair of (q,a)). Simply, we say that the Turing machine halts. As discussed earlier, if the machine halts in a final state, it accepts the input string. Otherwise, it rejects the input string.

Language acceptors VS. transducers

A Turing machine that accepts a specific language, similar to finite automata and PDAs, is called language acceptor.

A Turing machine that take an input string and transforms it to an output is called transducers.

Example

Let's take the language L={aⁿbⁿcⁿ | n ≥ 0} to help us understand what the concept of Turing machines is.

Before start trying to tackle this language and design a Turing machine for it, we should understand what string it contains. This language contains all ordered strings such that a's at the beginning of the string, b's at the middle and c's at the end where the number of a's, b's and c's match.

Our Turing machine should match one a with one b with one c and keep looping until the entire string is matched to accept the string. Here's a visualized of this procedure on the string aabbcc:

In the first iteration, the leftmost "a" will be converted to "A" symbol (can be any other symbol). Then the scanner will skip all small a's and convert the leftmost "b" to "B" symbol. Then the scanner will skip all small b's and convert the leftmost "c" to "C" symbol. After that, the scanner will go left skipping all "C" symbols, b's, "B" symbols and a's until it reaches an "A" symbol and it will go right to start the matching process again. At this point, the scanner will be on the left most "a" (note it's a small "a") and it'll proceeds as the first iteration with a minor difference is that the Turing machine will skip any "B" and "C" symbols. After the scanner finishes matching and goes back to the rightmost "A", it will move one cell to the right which is a cell that contains "B". When the scanner faces "B" symbol after moving on cell right, it's a sign that the string is matched. Then it will move to the right skipping all "B" and "C" symbols to verify that the b's and c's are all matched. The Turing machine will halt in a final state if after skipping all "B" and "C" symbols, the scanner reached a blank.

Here's the Turing machine design that accepts the Language L:

At the end of this post, I'd recommend a few resources if you'd like to acquire more knowledge about Turing machines:
1- Turing Machines published by Stanford
2- Turing Machines Explained - Computerphile
3- An Introduction to Formal Languages and Automata by Peter Linz

An Overview of Pushdown automata (PDA)

Hani — Tue, 24 Dec 2019 11:31:50 +0000

Let's take a look at the context-free language L={aⁿbⁿ | n ≥ 1}. How can we design a finite automaton (i.e. DFA/NFA) that accepts this language? To design a finite automaton that accepts this language, we should store the number of a's in some sort of memory in order to compare it to the number of b's. However, this's impossible due to the non-existence of memory in finite automata.

In this post, i'm going to walk you through the concept of PDAs and tackle how we can design machines that accept context-free languages.

Informal Definition
Formal Definition
Stack Manipulation
Non-deterministic VS. Deterministic PDAs
Example

Informal Definition

Let's think of PDAs as finite automata with a memory. This memory is simply a stack that can be manipulated as a part of the finite automata moves. The stack has initially a single symbol at the bottom of it which is denoted by Z (can be different in various textbooks).

Transitions in PDAs are of the form δ(q, a, A) contains (p, x) which means when you're in state q, if you see 'a' on input and A on top of stack:
• Go to state p
• Replace A on the stack with the string x (leftmost symbol of x is on top of the stack). Here's the above transition depicted:

Note that the colored parts in the stack indicate strings.

An input string is accepted if after the entire string is read, the PDA reaches a final state. It's important to mention that the stack contents are irrelevant to the acceptance of the string.

Formal Definition

Non-deterministic Push-Down Automaton is a septuple M = (Q, Σ, Γ, δ, q0, Z, F) where Q is a finite set of states
Σ is a finite input alphabet
Γ is a finite stack alphabet
q0 is the start state
Z ∈ Γ is the stack start symbol
F ⊆ Q is the set of final states
δ : Q × Σ U {λ} × Γ → finite set of subsets of Q × Γ^* is a transition function.

Language accepted by a PDA M = (Q, Σ, Γ, δ, q0, Z, F) is the set L(M) = {w ∈ Σ^* | (q0, w, Z) ⊢^∗ (p, λ, u), p ∈ F, u ∈ Γ^∗}

The PDA accepts all strings w for which you can reach the final
state at the end of the string (the stack contents are irrelevant).

Stack Manipulation

Let's say we have the following transition: δ(q, a, A) contains (p, x). The following table demonstrates how we'd manipulate the stack by replacing the x symbol by others. Note that A and B are single symbols and not strings and the red portion indicates that the stack contents can be anything (i.e. we only care about the top of the stack)!

x	Before	After	Meaning
λ			Pop the top of the stack
B			Replace "A" with "B"
BA			Push "B" on the top of "A"

How do we write the transition on the PDA graph? The answer is:
symbol you read, top of the stack, stack manipulation.
Example: a, A, B which means if you read an "a" and the top of the stack is "A", go to the state that the transition arrow points to and replace the "A" with "B" in the stack.

Non-deterministic VS. Deterministic PDAs

The only difference between NPDAs and DPDAs is that the latter has two restrictions:

δ(q, a, b) contains at most one element, so the following is prohibited in DPDAs
If δ(q, λ, b) is not empty, then δ(q, a, b) = Ø for all a ∈ Σ, so the following is prohibited in DPDAs

Unlike finite automata , not every NPDA has an equivalent DPDA. Therefore, the class of deterministic and non-deterministic languages are not equivalent.

Example

Let's take the language L={wcw^R | w ∈ (a+b)^∗} as an example. The general approach to design an NPDA for this language is to push all symbols you encounter until you encounter the symbol c which is a sign that the reverse string must occur. Then your NPDA should compare what is on the stack to what is being read until the stack is empty which is a sign that the w^R string has occurred.

Here's the NPDA design with a simulation for the input string abcba:

At the end of this post, I'd like to suggest a few resources that I think would be helpful if you want to acquire more knowledge about Pushdown automata:
1- Pushdown Automata: PDA-DPDA by Robert M. Kline
2- Pushdown Automata by Brilliant
3- An Introduction to Formal Languages and Automata by Peter Linz

Handling OS-level Authentication Dialogues in Internet Explorer using Selenium + AutoIt

Hani — Sun, 08 Sep 2019 18:09:24 +0000

For a few weeks, I've been working on a Selenium project and I'd to figure out a way to handle authentication dialogues in Internet Explorer (IE). The dilemma is that IE dialogues are non-browser dialogues, i.e., Windows-based dialogues. Therefore, they can't be handled using Selenium since Selenium doesn't recognize OS-level dialogues. I'll walk you through my solution which consists of two parts.

I used Selenium C# WebDriver. For other programming languages users, the concepts in this article are still applicable. You may need to import or use AutoIt package in a different way but nothing is really hard.

1- IE Settings:

I want IE to prompt the users to enter their credentials each time they open the browser because I'd like to run my tests against different users.

In your IE browser, click on Settings > Internet options > Security tab > check Enable Protected Mode > click on Custom level… > check Prompt for user name and password. Repeat the last three steps on all four zones (Internet, Local internet, Trusted sites, Restricted sites).

After applying the previous steps, IE should prompt the user to enter their credentials every time they open it.

2- C# code

To tackle the problem of Windows-based dialogues, I utilized a scripting language called AutoIt. By integrating AutoIt with Selenium, I was able to handle Windows- based dialogues smoothly. Let's dive into the C# code.

First step is to add AutoIt NuGet Package in Visual Studio. Refer to Microsoft Documentation. After referencing AutoIt NuGet Package (using AutoIt;), you will get a class named AutoItX with static methods ready to be used.

I created a method that takes the user credentials and handles the windows-based dialogues.

public static void SetAuthenticationCredentials(string UserName, string Pws)
        {
            AutoItX.WinWaitActive("Windows Security");
            AutoItX.Send(UserName);
            AutoItX.Send("{TAB}");
            AutoItX.Send(Pws);
            AutoItX.Send("{ENTER}");
        }

A number of people ran into an exception after this step, so here's one way to use the previous method properly.

Parallel.Invoke(() => driver.Navigate().GoToUrl("https://YourWebsite.com"), () => SetAuthenticationCredentials("usertest2", "password2"));

In this way, you'll navigate to your website and invoke the SetAuthenticationCredentials method simultaneously.

Congratulations!!! right now you should be able to handle Windows-based dialogues easily. If you have any question, please don't hesitate asking me.

Forem: Hani

An Overview of Turing Machines

Table of Contents

Informal Definition

Formal Definition

Transitions

Language acceptors VS. transducers

Example

An Overview of Pushdown automata (PDA)

Table of Contents

Informal Definition

Formal Definition

Stack Manipulation

Non-deterministic VS. Deterministic PDAs

Example

Handling OS-level Authentication Dialogues in Internet Explorer using Selenium + AutoIt